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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[][] Merge(int[][] intervals) {
6 Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
7 List<int[]> merged = new List<int[]>();
8 foreach (var interval in intervals) {
9 if (merged.Count == 0 || merged[^1][1] < interval[0]) {
10 merged.Add(interval);
11 }
12 else {
13 merged[^1][1] = Math.Max(merged[^1][1], interval[1]);
14 }
15 }
16 return merged.ToArray();
17 }
18}The Array.Sort method in C# allows us to sort intervals efficiently. Overlapping intervals are merged using a list that dynamically adjusts as needed.
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).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[][] Merge(int[][] intervals) {
6 Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
7 List<int[]> mergedIntervals = new List<int[]>();
8 int[] currentInterval = intervals[0];
9 mergedIntervals.Add(currentInterval);
10 foreach (var interval in intervals) {
11 if (currentInterval[1] < interval[0]) {
12 currentInterval = interval;
13 mergedIntervals.Add(currentInterval);
14 } else {
15 currentInterval[1] = Math.Max(currentInterval[1], interval[1]);
16 }
17 }
18 return mergedIntervals.ToArray();
19 }
20}Concentrate on correct sorting of intervals and assess whether it overlaps properly for each segment iteratively while forming the merged list sequentially.