56. Merge Intervals

Intuition

If intervals were sorted by start time, any two overlapping intervals would be adjacent. So sort first, then a single linear scan can greedily merge any interval that overlaps with the last recorded merged interval.

Algorithm

1Sort intervals by start value.
2Initialise the result list with the first interval.
3For each remaining interval [s, e]: if s <= result.Last.end (overlap), extend: result.Last.end = max(result.Last.end, e).
4Otherwise they do not overlap: push [s, e] as a new separate interval.
5Return the result list.

Example Walkthrough

Input: [[1,3],[2,6],[8,10],[15,18]]

1.Sort (already sorted). Start with result = [[1,3]].
2.[2,6]: start 2 <= 3 -> overlap. Extend: result = [[1,6]].
3.[8,10]: start 8 > 6 -> no overlap. Push: result = [[1,6],[8,10]].
4.[15,18]: start 15 > 10 -> no overlap. Push: result = [[1,6],[8,10],[15,18]].

Output: [[1,6],[8,10],[15,18]]

Common Pitfalls

•When extending, take max(current.end, new.end) - the new interval might be entirely contained inside the current one.
•Sorting by start is essential; without it, non-adjacent overlapping intervals are missed.

56.cs

// Approach: Sort all intervals by start value so that overlapping intervals become adjacent.
// Maintain a running merged interval (the last element in the result list).
// For each subsequent interval: if its start <= current end, they overlap — extend end if needed.
// If its start > current end, they do not overlap — push the current interval and start a new one.
// Sorting is the critical insight: without it we would need O(n^2) pairwise comparisons.
// Handle the edge case where the last running interval is never pushed (add it after the loop).
// Time: O(n log n) dominated by sort; merging is O(n). Space: O(n) for the result.

public class Solution
{
    public int[][] Merge(int[][] intervals)
    {
        List<int[]> mergedIntervals = new List<int[]>();

        if (intervals.Length == 0 || intervals == null)
        {
            return mergedIntervals.ToArray();
        }

        Array.Sort(intervals, (a, b) => a[0] - b[0]);

        int start = intervals[0][0];
        int end = intervals[0][1];

        for (int i = 0; i < intervals.Length; i++)
        {
            if (intervals[i][0] <= end)
            {
                end = Math.Max(end, intervals[i][1]);
            }
            else
            {
                mergedIntervals.Add(new int[] { start, end });
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        mergedIntervals.Add(new int[] { start, end });

        return mergedIntervals.ToArray();
    }
}

Was this solution helpful?