Interval Scheduling

Question 1

What is the first step in the Merge Intervals algorithm?

Accepted Answer

Sort intervals by start time — Sorting by start time ensures that any interval which could possibly overlap the current merged interval is processed immediately after it, allowing a single left-to-right sweep.

Question 2

Given intervals [[1,4],[4,5]], what does merge return?

Accepted Answer

[[1,5]] — The intervals share the boundary point 4 (start of second ≤ end of first), so they merge into [1,5].

Question 3

What is the time complexity of Merge Intervals on n intervals?

Accepted Answer

O(n log n) — the sort step dominates the linear sweep — Sorting takes O(n log n); the single sweep is O(n). The sort dominates, giving O(n log n) overall.

Question 4

Which condition triggers a merge (instead of pushing a new interval)?

Accepted Answer

current.start <= last.end — If the current interval's start is at or before the last merged interval's end, they overlap (or touch), so we extend the last interval's end to max(last.end, current.end).

Question 5

Which LeetCode problem is the canonical Merge Intervals question?

Accepted Answer

LC 56 — Merge Intervals — LC 56 (Merge Intervals) is the standard merge-intervals problem. LC 252 checks if a person can attend all meetings, LC 435 is activity selection, and LC 986 finds intersections between two lists.

Question 6

The Activity Selection greedy algorithm selects activities by earliest finishing time. Why does this greedy choice maximize the number of selected activities?

Accepted Answer

Earliest finish frees the resource soonest; the exchange argument proves swapping any later-finishing first pick for an earlier one never reduces the total count — The exchange argument: suppose a solution starts with an activity A that does NOT finish earliest. We can swap A for the earliest-finishing activity E without reducing the count (E finishes no later, so it conflicts with no more future activities than A). Repeating this argument shows any optimal solution can be transformed into one that always picks the earliest-finishing activity — proving the greedy choice is safe.

Question 7

Why does the greedy 'pick the highest-profit activity' approach FAIL for Weighted Interval Scheduling?

Accepted Answer

A single high-profit interval may block multiple non-overlapping intervals with higher total profit — DP evaluates the include/exclude tradeoff that greedy skips entirely — Consider: interval A (profit 10, time [1,10]) and intervals B, C, D (profit 4 each, times [1,3],[4,6],[7,9]). Greedy picks A for profit 10. DP picks B+C+D for profit 12. The greedy choice ignores the opportunity cost of blocking multiple non-overlapping alternatives. DP uses p(j) — the latest non-conflicting predecessor — to correctly evaluate the include-or-exclude decision for each interval.

Question 8

The Meeting Rooms II problem asks: given a list of meeting intervals, find the minimum number of conference rooms required. What is the key insight of the min-heap approach?

Accepted Answer

Keep a min-heap of room end-times; for each start-sorted meeting, reuse the room ending soonest if its end is ≤ meeting start, otherwise open a new room — Sort meetings by start time. Maintain a min-heap of end times of rooms currently in use. For each new meeting, if heap.min ≤ new.start, that room is free — pop and push the new end time (room reuse). Otherwise push the new end time (new room needed). Heap size at the end equals rooms needed. Time: O(n log n) for sorting + O(n log n) for n heap operations.

Question 9

In the Merge Intervals algorithm, the result list is built in-place using a write pointer. What is the auxiliary space complexity (space beyond the input and output)?

Accepted Answer

O(1) — only a write pointer index and current-interval bounds are needed; no auxiliary allocation grows with input size n — After sorting, a single write pointer (an integer index) tracks where the last merged interval ends. Each interval is compared against the current merged interval and either absorbed or appended — all in the same array. Only a constant number of variables (write pointer and current-interval bounds) are allocated outside the input/output arrays, giving O(1) auxiliary space.

Question 10

Should the intervals [1, 5] and [5, 10] be merged into [1, 10]?

Accepted Answer

Yes — they share the point 5, so they are touching intervals that should be merged into [1, 10] — In the standard Merge Intervals problem (LC 56), intervals are closed (endpoints included). Two intervals [a,b] and [c,d] overlap if c ≤ b (or equivalently, they should be merged if current.start ≤ last.end). Since 5 ≤ 5, [1,5] and [5,10] overlap and merge to [1,10]. The implementation condition is typically written as: if (current.start <= lastMerged.end) { merge } else { push new }.

Interval Scheduling: Merge Intervals

Merge the intervals

Test your knowledge

What is the first step in the Merge Intervals algorithm?

Write the code

Merge Intervals

Example Cases

The short version

In more depth

Merging Intervals

Why sorting comes first

The merge sweep

The variants share the skeleton

Interview Questions

References & Further Reading

Love this visualization?