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.
Another approach involves consecutive comparisons and inserting intervals into a new list if they do not overlap with the current interval being processed.
Time Complexity: O(n log n).
Space Complexity: O(n).
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class Solution {
6 public int[][] merge(int[][] intervals) {
7 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
8 List<int[]> result = new ArrayList<>();
9 int[] currentInterval = intervals[0];
10 result.add(currentInterval);
11 for (int[] interval : intervals) {
12 if (currentInterval[1] < interval[0]) {
13 currentInterval = interval;
14 result.add(currentInterval);
15 } else {
16 currentInterval[1] = Math.max(currentInterval[1], interval[1]);
17 }
18 }
19 return result.toArray(new int[result.size()][]);
20 }
21}Java solution revolves around sorting and sequentially adding checked intervals to the output list after comparing endpoints to ensure no overlaps.