Merge Intervals

1. Merge Intervals Medium

Problem

Given a list of intervals, merge all overlapping ones and return the non-overlapping intervals that cover exactly the same ground. For [[1,3],[2,6],[8,10],[15,18]] the answer is [[1,6],[8,10],[15,18]].

Approach

• Sort by start. Now anything that can merge with the range under construction comes next in the list.
• Carry one open range. Each new interval either extends it or closes it and opens a new one.

Solution

public static class MergeIntervals
{
    /// <summary>Merge every set of overlapping intervals into one.</summary>
    /// <param name="intervals">Pairs [start, end] with start &lt;= end, in any order.
    /// Sorted in place as a side effect.</param>
    /// <returns>Disjoint intervals in increasing order covering the same union.</returns>
    /// <example><c>Merge([[1, 3], [2, 6], [8, 10], [15, 18]])</c>
    /// returns [[1, 6], [8, 10], [15, 18]].</example>
    public static int[][] Merge(int[][] intervals)
    {
        if (intervals.Length == 0)
            return [];                       // nothing to merge

        // a[0]: the start. Sorted by start, any overlap is with the last merged one.
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        // [0]: the first interval seeds the output. A fresh array, so no aliasing.
        List<int[]> merged = [[intervals[0][0], intervals[0][1]]];

        // i: index of the incoming interval. 1: index 0 is already in merged.
        // Invariant: merged is the sorted, disjoint union of intervals[0..i-1].
        for (int i = 1; i < intervals.Length; i++)
        {
            int start = intervals[i][0], end = intervals[i][1];   // [0] start, [1] end
            int[] last = merged[^1];         // ^1: the interval still being built

            // last[1]: its end. A start at or before it means overlap.
            if (start <= last[1])
            {
                // Overlaps or touches. Extend, but never shrink: the incoming
                // interval may sit entirely inside the one we are building.
                last[1] = Math.Max(last[1], end);
            }
            else
            {
                merged.Add([start, end]);    // a gap: open a new merged interval
            }
        }

        return merged.ToArray();
    }
}

Walkthrough

[[1,3],[2,6],[8,10],[15,18]], already sorted by start:

• Incoming [2, 6]. last is [1, 3]. 2 ≤ 3, so they overlap. last becomes [1, 6].
• Incoming [8, 10]. last is [1, 6]. 8 > 6, so they are disjoint. Emit and open [8, 10].
• Incoming [15, 18]. last is [8, 10]. 15 > 10, so they are disjoint. Emit and open [15, 18].

Reading the figure. Amber is last, the range being built. Blue is the incoming interval. Green ranges are finished and emitted. An incoming start at or before the end of last extends it.

Edge cases to raise

• Nested interval, [[1, 10], [2, 3]]: must give [[1, 10]]. This is the max test.
• Touching intervals, [[1, 4], [4, 5]]: with ≤ they merge to [[1, 5]]. Confirm which behaviour is wanted.
• Single interval, or empty input.
• Duplicate intervals: merge into one, no special handling needed.

2. Insert Interval Medium

Problem

You are given a list of already sorted, non-overlapping intervals and one new interval. Insert it, merging where needed, and return the result still sorted and non-overlapping.

Approach

• The input is already sorted, so there is no sort. The solution is O(n), and saying that is the point of the problem: the interviewer wants to see that you do not pay for a sort you do not need.
• Three clean phases, in order:
  1. Copy every interval that ends strictly before the new one starts. Untouched.
  2. Absorb every interval that overlaps the new one, widening the new interval’s start and end as you go. Emit it once.
  3. Copy the rest. Untouched.
• Writing it as three sequential while loops rather than one loop with flags is what makes it readable.

Solution

public static class InsertInterval
{
    /// <summary>Insert one interval into a sorted, disjoint list, merging as needed.</summary>
    /// <param name="intervals">Sorted, pairwise non-overlapping [start, end] pairs.</param>
    /// <param name="newInterval">The interval to add.</param>
    /// <returns>A new array, still sorted and non-overlapping.</returns>
    /// <example><c>Insert([[1, 3], [6, 9]], [2, 5])</c> returns [[1, 5], [6, 9]].</example>
    public static int[][] Insert(int[][] intervals, int[] newInterval)
    {
        int start = newInterval[0], end = newInterval[1];   // [0] start, [1] end
        var output = new List<int[]>();
        int i = 0, n = intervals.Length;     // 0: scan from the first interval

        // Phase 1: everything that finishes before the new interval begins.
        // [i][1]: the end of interval i. It ends before start, so no overlap.
        while (i < n && intervals[i][1] < start)
        {
            output.Add(intervals[i]);
            i++;                             // +1: move to the next interval
        }

        // Phase 2: everything that overlaps. Widen, then emit once.
        // [i][0]: the start of interval i. At or before end means overlap.
        while (i < n && intervals[i][0] <= end)
        {
            start = Math.Min(start, intervals[i][0]);   // [0]: grow left to the earlier start
            end = Math.Max(end, intervals[i][1]);       // [1]: grow right to the later end
            i++;                             // +1: this one is absorbed, move on
        }
        output.Add([start, end]);

        // Phase 3: everything that starts after the merged interval ends.
        while (i < n)
        {
            output.Add(intervals[i]);
            i++;                             // +1: move to the next interval
        }

        return output.ToArray();
    }
}

Walkthrough

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], inserting [4, 8]:

• Phase 1. Handles [1, 2]. 2 < 4, so it is copied.
• Phase 2. Handles [3, 5], [6, 7], [8, 10]. The new interval grows 4→3 then 8→10, and emits [3, 10].
• Phase 3. Handles [12, 16]. It is copied.

Reading the figure. Blue bars are copied as they are. Amber is the new interval as it grows. Red dashed bars are absorbed into it. Green is the result, still sorted and non-overlapping.

Result: [[1,2],[3,10],[12,16]].

Edge cases to raise

• New interval before everything: phase 1 and 2 do nothing, it is emitted first.
• New interval after everything: phases 1 and 3 handle it, phase 2 does nothing.
• Empty input list: returns just the new interval.
• New interval swallowed by an existing one, such as inserting [2, 3] into [[1, 10]]: phase 2 widens it back out to [1, 10]. Verify this case, it is the one people get wrong.

3. Non-overlapping Intervals Medium

Problem

Given a list of intervals, return the minimum number to remove so that the rest are pairwise non-overlapping.

Approach

• Flip the question. Removing the fewest is the same as keeping the most. That reframing is the whole problem, and it turns it into the classic activity selection problem.
• Sort by end time, not start. Then greedily keep any interval that starts at or after the last kept end.
• Answer is intervals.Length - kept.

Why sorting by end is optimal

Solution

public static class EraseOverlapIntervals
{
    /// <summary>Fewest intervals to delete so the remainder are pairwise disjoint.</summary>
    /// <param name="intervals">Pairs [start, end]. Sorted in place as a side effect.</param>
    /// <returns>The number of intervals that must be removed.</returns>
    /// <example><c>MinRemovals([[1, 2], [2, 3], [3, 4], [1, 3]])</c> returns 1.</example>
    public static int MinRemovals(int[][] intervals)
    {
        if (intervals.Length == 0)
            return 0;                        // 0: nothing to remove

        // Earliest finishing time first: it leaves the most room for what follows.
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));   // a[1]: the end

        int kept = 1;                        // 1: the earliest-finishing one is always kept
        int lastEnd = intervals[0][1];       // [0][1]: end of that first kept interval

        // i: index of the interval being judged. 1: index 0 is already kept.
        // Invariant: kept is the most disjoint intervals among intervals[0..i-1].
        for (int i = 1; i < intervals.Length; i++)
        {
            if (intervals[i][0] >= lastEnd)  // touching is allowed, so >= not >
            {
                kept++;                      // +1: keep this one too
                lastEnd = intervals[i][1];   // [1]: the new finish line to beat
            }
        }

        // Removing the fewest is the same as keeping the most.
        return intervals.Length - kept;
    }
}

Walkthrough

[[1,2],[2,3],[3,4],[1,3]] sorted by end becomes [[1,2],[1,3],[2,3],[3,4]]:

• [1, 2]. No lastEnd yet. Keep, it is the seed. kept = 1.
• [1, 3]. lastEnd = 2. 1 < 2 is a conflict, so drop. kept = 1.
• [2, 3]. lastEnd = 2. 2 ≥ 2, so keep. kept = 2.
• [3, 4]. lastEnd = 3. 3 ≥ 3, so keep. kept = 3.

Reading the figure. Rows are in end order. The amber line is lastEnd when that row is checked. A bar that starts left of the line overlaps and turns red. Green bars are kept.

Kept 3 of 4, so remove 1.

Edge cases to raise

• Empty or single interval: remove 0.
• All identical intervals: keep 1, remove n - 1.
• Already disjoint: remove 0.
• Touching intervals count as non-overlapping here, hence >=. Confirm this reading with the interviewer.

4. Meeting Rooms II Medium

Problem

Given meeting time intervals, return the minimum number of conference rooms needed to hold them all. A meeting that ends at time t frees its room for a meeting starting at t.

Approach

• The answer is the maximum number of meetings running at the same instant. Once you say that sentence, both solutions below are obvious.
• Heap solution. Sort by start. Keep a PriorityQueue<int, int> of the end times of meetings in rooms. It is a min-heap, so the earliest end is on top. For each new meeting, reuse the earliest-ending room if it is already free. Otherwise open a new room. The heap size at the end is the answer.
• Sweep-line solution. Split each meeting into a +1 at its start and a -1 at its end, sort all events, and track the running total. Simpler, and the one to reach for if the heap feels heavy.

Solution: heap of end times

public static class MeetingRooms
{
    /// <summary>Minimum rooms needed so no two meetings share a room.</summary>
    /// <param name="intervals">Pairs [start, end] with start &lt; end.
    /// Sorted in place as a side effect.</param>
    /// <returns>The peak number of simultaneously running meetings.</returns>
    /// <example><c>MinRooms([[0, 30], [5, 10], [15, 20]])</c> returns 2.</example>
    public static int MinRooms(int[][] intervals)
    {
        if (intervals.Length == 0)
            return 0;                        // 0: no meetings, no rooms

        // a[0]: the start. Hand out rooms in the order meetings begin.
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        // Min-heap of end times. Element and priority are both the end time.
        // The top is the room that frees up soonest.
        var rooms = new PriorityQueue<int, int>();

        // Invariant: rooms holds one end time per room opened so far.
        foreach (int[] meeting in intervals)
        {
            int start = meeting[0], end = meeting[1];   // [0] start, [1] end
            // Peek: the earliest end. At or before start means that room is free.
            if (rooms.TryPeek(out _, out int earliest) && earliest <= start)
                rooms.DequeueEnqueue(end, end);   // reuse: pop the free room, push ours
            else
                rooms.Enqueue(end, end);          // every room is busy, open one more
        }

        return rooms.Count;                  // rooms never close, so the count is the peak
    }
}

Solution: sweep line

public static class MeetingRoomsSweep
{
    /// <summary>Same answer via a sweep over start and end events.</summary>
    /// <param name="intervals">Pairs [start, end].</param>
    /// <returns>The peak number of rooms in use at once.</returns>
    /// <example><c>MinRooms([[0, 30], [5, 10], [15, 20]])</c> returns 2.</example>
    public static int MinRooms(int[][] intervals)
    {
        // Two events per meeting. * 2: one start and one end each.
        var events = new (int Time, int Delta)[intervals.Length * 2];
        for (int i = 0; i < intervals.Length; i++)
        {
            events[2 * i] = (intervals[i][0], 1);        // 2 * i: even slot. 1: room in use
            events[2 * i + 1] = (intervals[i][1], -1);   // + 1: odd slot. -1: room frees
        }

        // Sorting tuples puts (t, -1) before (t, 1), so a room freed at time t
        // is available to a meeting starting at t. That is the tie-break we want.
        Array.Sort(events);

        int running = 0, best = 0;           // 0: no rooms in use before the first event
        // delta: 1 or -1 from above. The time is not needed once sorted.
        // Invariant: running is the rooms in use just after this event.
        foreach (var (_, delta) in events)
        {
            running += delta;
            best = Math.Max(best, running);  // keep the peak
        }

        return best;
    }
}

Walkthrough

[[0, 30], [5, 10], [15, 20]], heap version:

• Meeting [0, 30]. The queue is empty. Open a room. Queue after: [30].
• Meeting [5, 10]. Earliest end 30. 30 > 5, still busy, so open. Queue after: [10, 30].
• Meeting [15, 20]. Earliest end 10. 10 ≤ 15, so reuse. Queue after: [20, 30].

Reading the figure. Blue bars open a room. The green bar reuses a room, since the earliest end in the heap was 10 and 10 ≤ 15. The amber line marks time 15. The boxes show the PriorityQueue of end times after each meeting.

Two rooms.

Both solutions are dominated by the sort. The heap holds at most one entry per concurrent meeting.

Edge cases to raise

• Empty list: 0 rooms.
• Back-to-back meetings, [[1, 5], [5, 9]]: one room, because of ≤ in the heap version and the tuple tie-break in the sweep. This is the case that separates the two readings of “overlap”.
• All meetings identical: n rooms.
• Zero-length meetings, if allowed: the sweep handles them, the heap needs a moment’s thought. Ask whether they can occur.