Intervals
Ranges with a start and end — sorting by start (or end) turns overlap and merge problems into a single linear pass.
Try answering in your head first, then click a question to check the model answer.
Q1.Why must intervals be sorted by start time before merging overlapping ones?(show answer)
Once sorted by start, you only need to compare each interval to the last merged interval so far — if it overlaps, extend that interval's end if needed; if not, it starts a genuinely new group. Without sorting, an interval that overlaps an earlier one could appear anywhere in the list, forcing an O(n²) comparison of every pair instead of a single O(n) linear pass after the O(n log n) sort.
Q2.Walk through the algorithm for merging a list of overlapping intervals.(show answer)
Sort intervals by start time. Initialize the result with the first interval. For each subsequent interval, compare its start to the end of the last interval in the result: if the current interval's start is less than or equal to that end, they overlap — merge by extending the result's last interval's end to the max of the two ends. Otherwise, append the current interval as a new, separate entry in the result.
Q3.How would you determine the minimum number of meeting rooms needed to schedule all given meetings without conflict?(show answer)
Separate all start times and end times into two sorted arrays. Sweep through in time order using two pointers: whenever a meeting starts, increment a room counter; whenever a meeting ends, decrement it. Track the maximum value the counter reaches — that's the minimum rooms needed, since it represents the peak number of simultaneously overlapping meetings at any point in time.
Q4.Why is checking every pair of intervals for overlap an inefficient approach compared to the sort-based techniques?(show answer)
Checking every pair is O(n²), which becomes slow for large interval sets. Sorting first (O(n log n)) restructures the problem so that overlap-related questions — merging, counting concurrent intervals, finding gaps — can be answered with a single linear sweep afterward (O(n)), since sorted order guarantees you only ever need to compare an interval to its immediate neighbor(s) in the sweep, not every other interval in the set.