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 <= 104The key idea in Merge Intervals is to combine overlapping intervals into a single continuous range. A common strategy is to first sort the intervals by their starting time. Sorting ensures that any overlapping intervals will appear next to each other, making them easier to merge.
After sorting, iterate through the intervals and maintain a result list. Compare the current interval with the last interval stored in the result. If the intervals overlap (i.e., the current start is less than or equal to the previous end), merge them by updating the end value using max(end1, end2). Otherwise, simply append the current interval to the result.
This greedy approach works because once intervals are sorted, each interval only needs to be compared with the last merged interval. The overall time complexity is dominated by the sorting step, while the merging pass is linear.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sort intervals and merge overlapping ranges | O(n log n) | O(n) |
take U forward
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.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), required for the output array.
1#include <stdlib.h>
2#include <string.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int **)a)[0] - (*(int **)b)[0];
6}
7
8int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
9 if (intervalsSize == 0) {
10 *returnSize = 0;
11 return NULL;
12 }
13 qsort(intervals, intervalsSize, sizeof(int*), compare);
14 int** result = (int**)malloc(intervalsSize * sizeof(int*));
15 *returnColumnSizes = (int*)malloc(intervalsSize * sizeof(int));
16 int index = 0;
17 for (int i = 0; i < intervalsSize; ++i) {
18 if (index == 0 || result[index - 1][1] < intervals[i][0]) {
19 result[index] = (int*)malloc(2 * sizeof(int));
20 result[index][0] = intervals[i][0];
21 result[index][1] = intervals[i][1];
22 (*returnColumnSizes)[index] = 2;
23 index++;
24 } else {
25 result[index - 1][1] = result[index - 1][1] > intervals[i][1] ? result[index - 1][1] : intervals[i][1];
26 }
27 }
28 *returnSize = index;
29 return result;
30}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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Merge Intervals is a classic interval problem frequently asked in technical interviews at companies like Google, Amazon, and Facebook. It tests understanding of sorting, greedy strategies, and interval manipulation.
Sorting ensures that intervals are processed in increasing order of their start times. This guarantees that any overlapping intervals appear next to each other, allowing us to merge them with a simple linear scan.
The optimal approach is to first sort the intervals based on their start time and then iterate through them while merging overlapping intervals. By maintaining a result list and updating the end time when overlaps occur, the problem can be solved efficiently in a single pass after sorting.
Arrays or lists are typically used to store intervals and the merged results. Since we process intervals sequentially after sorting, a dynamic list structure works well for appending or updating merged ranges.
This method involves sorting first and directly inserting into the result list, verifying overlap in consecutive intervals.