Merge Intervals medium

Problem Statement

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] overlaps, 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.

Steps

1. Sort the intervals: Sort the intervals based on their start times. This step is crucial for efficient merging. We can use a custom comparer or LINQ's OrderBy method.

2. Initialize the result: Create a list to store the merged intervals. Add the first interval from the sorted list to the result.

3. Iterate and merge: Iterate through the sorted intervals, starting from the second one.

   • Compare the current interval's start time with the last interval in the result's end time.
   • If they overlap (current interval's start is less than or equal to the last interval's end), merge them: Update the last interval's end time to the maximum of the current interval's end time and the last interval's end time.
   • If they don't overlap, add the current interval to the result.

4. Return the result: Return the list of merged intervals.

Explanation

The algorithm leverages the fact that if intervals are sorted by their start times, overlapping intervals will always appear consecutively. By iterating through the sorted intervals and comparing the current interval with the last merged interval, we can efficiently identify and merge overlapping intervals. The sorting ensures we consider intervals in the correct order to avoid missing overlaps.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals == null || intervals.Length == 0) {
            return new int[0][]; //Return empty array if input is null or empty
        }

        // Sort intervals by start time
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        List<int[]> mergedIntervals = new List<int[]>();
        mergedIntervals.Add(intervals[0]); // Add the first interval

        foreach (int[] interval in intervals.Skip(1)) {
            int[] lastMergedInterval = mergedIntervals.Last();
            if (interval[0] <= lastMergedInterval[1]) { // Overlap
                lastMergedInterval[1] = Math.Max(lastMergedInterval[1], interval[1]); // Merge
            } else {
                mergedIntervals.Add(interval); // No overlap, add new interval
            }
        }

        return mergedIntervals.ToArray();
    }
}

Complexity

• Time Complexity: O(n log n), dominated by the sorting step.
• Space Complexity: O(n) in the worst case (no overlaps), where n is the number of intervals. The space used by the mergedIntervals list could be at most the size of the input array.