Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104Problem Overview: You receive a list of intervals where each interval represents a start and end time. Some intervals overlap. Your task is to merge all overlapping intervals and return a list of non‑overlapping intervals that cover the same ranges.
Approach 1: Sort and Merge Intervals (Time: O(n log n), Space: O(n))
The standard solution sorts intervals by their starting value, then performs a single linear scan to merge overlaps. Sorting ensures that if two intervals overlap, they appear next to each other. Start with the first interval and treat it as the current merged range. As you iterate through the sorted list, compare the current interval's start with the previous merged interval's end.
If the intervals overlap (current.start <= last.end), update the merged interval's end using max(last.end, current.end). If they do not overlap, push the previous interval into the result and start a new merged interval. This produces the minimal set of merged ranges in one pass after sorting. The algorithm relies on sorting followed by sequential processing of an array. Time complexity is O(n log n) due to sorting, while the merge scan itself is O(n). Space complexity is O(n) for the output list.
Approach 2: Interval Insertion Method (Time: O(n log n), Space: O(n))
This method treats the problem similarly to repeatedly inserting intervals into a merged result set. First sort the intervals by start time. Then iterate through them while maintaining a result list of non‑overlapping intervals. For each new interval, check whether it overlaps with the last interval already stored.
If there is no overlap (interval.start > result[-1].end), append it directly to the result. If an overlap exists, merge by expanding the end of the previous interval: result[-1].end = max(result[-1].end, interval.end). Conceptually, this approach views merging as incremental interval insertion into a maintained structure.
The advantage is conceptual clarity: the result array always stays valid and merged. The algorithm still requires sorting first, so the overall complexity remains O(n log n) time with O(n) space. The iteration step itself is linear.
Recommended for interviews: Interviewers typically expect the Sort and Merge approach. It demonstrates knowledge of sorting combined with linear scanning and interval reasoning. Explaining the overlap condition and why sorting guarantees adjacent overlaps shows strong problem‑solving skills. A brute force pairwise comparison would work but leads to O(n^2) complexity and signals weaker optimization awareness.
The key to solving this problem is to first sort the intervals based on the starting time. Once sorted, we can iterate over the intervals and merge them if they overlap. Two intervals overlap if the start of the current interval is less than or equal to the end of the previous interval.
In C, sorting is performed using qsort, with a custom comparator function. We iterate through each interval and merge overlapping intervals into a single one, storing the results in a new 2D array.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), required for the output array.
Another approach involves consecutive comparisons and inserting intervals into a new list if they do not overlap with the current interval being processed.
This method involves sorting first and directly inserting into the result list, verifying overlap in consecutive intervals.
Time Complexity: O(n log n).
Space Complexity: O(n).
We can sort the intervals in ascending order by the left endpoint, and then traverse the intervals for merging operations.
The specific merging operation is as follows.
First, we add the first interval to the answer. Then, we consider each subsequent interval in turn:
Finally, we return the answer array.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of intervals.
| Approach | Complexity |
|---|---|
| Sort and Merge Intervals | Time Complexity: O(n log n), due to sorting. |
| Interval Insertion Method | Time Complexity: O(n log n). |
| Sorting + One-pass Traversal | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Merge Intervals | O(n log n) | O(n) | General case where intervals are unsorted. Most common and interview‑expected solution. |
| Interval Insertion Method | O(n log n) | O(n) | When building a merged result incrementally while iterating through sorted intervals. |
Merge Intervals - Sorting - Leetcode 56 • NeetCode • 246,516 views views
Watch 9 more video solutions →Practice Merge Intervals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor