Q: In `minMeetingRooms`, why does incrementing `rooms` when `starts[s] < ends[e]` (strictly less than, not less-than-or-equal) correctly determine that a new room is needed?

A new meeting starting strictly before the earliest currently-ongoing meeting ends means both meetings are genuinely occupying overlapping time at that instant, so the existing room(s) can't be reused yet — a new one is needed. If a meeting instead starts exactly when another ends, that room has just freed up and can be reused instead of counted as a conflict. — The strict `<` matters: if a new meeting starts at the exact same time an ongoing one ends, that room is free at that instant and can be reused — no additional room is needed, which is why that case falls into the `else` (decrement) branch instead. Only a start that occurs strictly before the earliest end genuinely overlaps with ongoing meetings, requiring a new room. Option B is incorrect — switching to `<=` would cause the algorithm to overcount rooms in the touching-boundary case, changing the result. Option C misdescribes the code; the `if`/`else` structure controls whether `rooms` is incremented or decremented, not merely whether `maxRooms` is updated (that update happens unconditionally after either branch). Option D fabricates an unrelated "priority" concept that doesn't exist in this problem.

Q: According to the module, what is the core idea behind the "line sweep" technique that makes `minMeetingRooms` O(n log n) instead of the O(n²) an all-pairs overlap check would require?

Separating events (starts and ends) into sorted lists and processing them in time order while maintaining a single running counter, rather than comparing every interval against every other interval directly to check for overlaps. — The module explicitly frames line sweep as decomposing intervals into individual start/end events, sorting those events by time, and sweeping through them with a running counter that increments on starts and decrements on ends — tracking the peak value reached. This avoids ever directly comparing one interval to another; the overlap information falls out of the running count instead. Option B fabricates a parallelism claim; the technique described is a single sequential pass, not concurrent execution. Option C is incorrect and would miss overlaps entirely — every event is processed, not just the first and last. Option D is wrong — the module explicitly sorts `starts` and `ends` before sweeping; the O(n log n) complexity comes directly from that sort step, with the sweep itself being O(n).

Question 1

In `mergeIntervals`, why is sorting the intervals by start time a required first step, rather than an optional optimization?

Accepted Answer

The merge pass only ever compares each interval to the single most recently merged interval — this is only guaranteed to catch every actual overlap if the intervals are processed in sorted start order, so that any interval capable of overlapping a given one is guaranteed to be adjacent to it in the processing order. — The merge loop only checks `current[0] <= last[1]` against the most recently merged interval, not every previously seen interval. This shortcut is only valid because sorting by start time guarantees that if two intervals overlap, they'll be encountered in an order where the check against just the immediate predecessor is sufficient — an unsorted list could have overlapping intervals separated by non-overlapping ones in between, which this single-predecessor check would miss entirely. Option A is false — on unsorted input, the same logic would silently produce incorrect, incompletely-merged results rather than an equivalent answer. Option C misattributes the requirement to TypeScript's type system, which has no bearing on this algorithmic necessity. Option D is incorrect — running the function on unsorted input does not throw; it simply produces a wrong (under-merged) result silently.

Question 2

In `minMeetingRooms`, why does incrementing `rooms` when `starts[s] < ends[e]` (strictly less than, not less-than-or-equal) correctly determine that a new room is needed?

Accepted Answer

A new meeting starting strictly before the earliest currently-ongoing meeting ends means both meetings are genuinely occupying overlapping time at that instant, so the existing room(s) can't be reused yet — a new one is needed. If a meeting instead starts exactly when another ends, that room has just freed up and can be reused instead of counted as a conflict. — The strict `<` matters: if a new meeting starts at the exact same time an ongoing one ends, that room is free at that instant and can be reused — no additional room is needed, which is why that case falls into the `else` (decrement) branch instead. Only a start that occurs strictly before the earliest end genuinely overlaps with ongoing meetings, requiring a new room. Option B is incorrect — switching to `<=` would cause the algorithm to overcount rooms in the touching-boundary case, changing the result. Option C misdescribes the code; the `if`/`else` structure controls whether `rooms` is incremented or decremented, not merely whether `maxRooms` is updated (that update happens unconditionally after either branch). Option D fabricates an unrelated "priority" concept that doesn't exist in this problem.

Question 3

According to the module, what is the core idea behind the "line sweep" technique that makes `minMeetingRooms` O(n log n) instead of the O(n²) an all-pairs overlap check would require?

Accepted Answer

Separating events (starts and ends) into sorted lists and processing them in time order while maintaining a single running counter, rather than comparing every interval against every other interval directly to check for overlaps. — The module explicitly frames line sweep as decomposing intervals into individual start/end events, sorting those events by time, and sweeping through them with a running counter that increments on starts and decrements on ends — tracking the peak value reached. This avoids ever directly comparing one interval to another; the overlap information falls out of the running count instead. Option B fabricates a parallelism claim; the technique described is a single sequential pass, not concurrent execution. Option C is incorrect and would miss overlaps entirely — every event is processed, not just the first and last. Option D is wrong — the module explicitly sorts `starts` and `ends` before sweeping; the O(n log n) complexity comes directly from that sort step, with the sweep itself being O(n).

Module F-10 — Intervals and Line Sweep

Representing Intervals

Merging Overlapping Intervals

Line Sweep: Counting Overlaps at Any Moment

Inserting Into an Already-Merged List

Where This Shows Up in Your Stack

Summary

Test your knowledge with more question sets

Sign in to keep reading

Discussion