Loading problems...
TL;DR: Sort the intervals by their start times, then iterate through the list, merging overlapping intervals by extending the end time of the current interval to the maximum end time found.
The Merge Intervals problem requires taking a collection of time intervals, each defined by a start and an end point, and consolidating any overlapping intervals into a single, continuous interval. The goal is to produce a list of non-overlapping intervals that cover the exact same total range as the input.
This is a fundamental problem in array manipulation and scheduling algorithms. Finding the optimal LeetCode 56 Solution is a common requirement in technical interviews for major tech companies, as it tests the ability to handle sorting and greedy logic efficiently.
A naive approach to solving Merge Intervals involves treating the intervals as a graph problem. We can consider each interval as a node in a graph. An undirected edge exists between two nodes if the corresponding intervals overlap.
The algorithm would proceed as follows:
[min(starts), max(ends)].Pseudo-code:
function bruteForce(intervals):
graph = buildGraph(intervals) // O(N^2) comparisons
components = findConnectedComponents(graph)
result = []
for component in components:
minStart = infinity
maxEnd = -infinity
for interval in component:
minStart = min(minStart, interval.start)
maxEnd = max(maxEnd, interval.end)
result.add([minStart, maxEnd])
return resultComplexity Analysis: The time complexity is dominated by building the graph, which requires comparing every interval with every other interval, resulting in O(N²) time complexity. While might theoretically pass within a generous time limit, this approach is highly inefficient and needlessly complex to implement compared to the optimal sorting approach.
The primary obstacle in the brute force approach is that intervals appear in random order. To determine if an interval merges with any other, we must scan the entire list.
The core insight that optimizes this process is sorting. If we sort the intervals based on their start times, we gain a powerful property: for any interval current, the only intervals that can merge with it are those that appear directly after it in the sorted list. We never need to look backward.
Once sorted, we can iterate through the list linearly. We maintain a last_merged interval. When we encounter a new interval, there are only two possibilities:
last_merged interval ends. Because the list is sorted by start time, we know the new interval started after the last_merged interval started. Therefore, they must overlap. We greedily extend the last_merged interval's end time.last_merged interval ends. We finalize the last_merged interval and start a new merge chain with the current interval.Visual Description: Imagine the intervals plotted on a 1D coordinate line. Sorting aligns them from left to right based on their left-most point. As the algorithm scans from left to right, it maintains a "coverage window." If the next segment on the line begins within the current coverage window, the window extends to include the furthest point of that segment. If the next segment begins outside the window, the current window is closed (saved), and a new window begins at the start of the new segment.

Consider the input: [[1,3], [8,10], [2,6], [15,18]]
[[1,3], [2,6], [8,10], [15,18]].merged = [[1,3]].[2,6]):
[1,3].[2,6].2 <= 3? Yes.max(3, 6).merged is now [[1,6]].[8,10]):
[1,6].[8,10].8 <= 6? No.[8,10] to merged.merged is now [[1,6], [8,10]].[15,18]):
[8,10].[15,18].15 <= 10? No.[15,18] to merged.merged is now [[1,6], [8,10], [15,18]].[[1,6], [8,10], [15,18]].The correctness relies on the sorted order of start times. Let the sorted intervals be . If overlaps with , then . Since we sorted by start time, we also know . The union of these two intervals is strictly . Because the list is sorted, no interval (where ) can start before . Therefore, we can safely merge into the running interval without checking future intervals. If a future interval overlaps with the newly merged interval, it will be caught in subsequent iterations because the "active" interval has been extended. This greedy choice property ensures we never miss a merge and never merge non-overlapping intervals.
cppclass Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.empty()) { return {}; } // 1. Sort intervals by start time sort(intervals.begin(), intervals.end()); vector<vector<int>> merged; // Initialize with the first interval merged.push_back(intervals[0]); // 2. Iterate through the rest for (int i = 1; i < intervals.size(); ++i) { // Reference to the last interval in the merged list // Using reference allows us to modify it in place vector<int>& last = merged.back(); // Current interval boundaries int currentStart = intervals[i][0]; int currentEnd = intervals[i][1]; if (currentStart <= last[1]) { // Overlap: extend the end of the last interval last[1] = max(last[1], currentEnd); } else { // No overlap: add the new interval merged.push_back(intervals[i]); } } return merged; } };
javaclass Solution { public int[][] merge(int[][] intervals) { if (intervals.length <= 1) { return intervals; } // 1. Sort intervals by start time using a lambda comparator Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>(); // Initialize with the first interval int[] currentInterval = intervals[0]; merged.add(currentInterval); // 2. Iterate through the rest for (int[] interval : intervals) { int currentEnd = currentInterval[1]; int nextStart = interval[0]; int nextEnd = interval[1]; if (nextStart <= currentEnd) { // Overlap: update the end of the current interval // We modify the array inside the list directly currentInterval[1] = Math.max(currentEnd, nextEnd); } else { // No overlap: move to the next interval currentInterval = interval; merged.add(currentInterval); } } // Convert List<int[]> back to int[][] return merged.toArray(new int[merged.size()][]); } }
pythonclass Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if not intervals: return [] # 1. Sort intervals by start time intervals.sort(key=lambda x: x[0]) merged = [intervals[0]] # 2. Iterate through the rest for current_start, current_end in intervals[1:]: last_end = merged[-1][1] if current_start <= last_end: # Overlap: update the end of the last interval merged[-1][1] = max(last_end, current_end) else: # No overlap: append the new interval merged.append([current_start, current_end]) return merged
Time Complexity: The dominant operation is sorting the intervals, which takes . The subsequent linear scan to merge intervals takes time, as we visit each interval exactly once. Thus, the total time complexity is .
Space Complexity: or The space complexity depends on the implementation of the sorting algorithm.
Arrays.sort (Dual-Pivot Quicksort) typically uses stack space.sort (Timsort) can use space.std::sort (Introsort) uses stack space.The Greedy - Interval Merging/Scheduling pattern is highly reusable. If you master LeetCode 56, you can apply similar logic to:
Why do I get Wrong Answer on inputs like [[1,4], [2,3]]?
last.end = current.end).max(last.end, current.end). In [[1,4], [2,3]], the merged interval is [1,4], not [1,3].Why is my solution failing on large inputs (Time Limit Exceeded)?
merged list which stores the output. If we consider the output space, it is . If we ignore output space (auxiliary space only), it is determined by the sort.Why am I getting Index Out of Bounds errors?
intervals list (deleting elements) while iterating over it.merged) and append to it. Never modify the list you are actively iterating through unless you are very careful with indices.Why does my code fail on unsorted inputs?