Interval Problems in Coding Interviews: Merge, Insert, Overlap, and Meeting Rooms

Interval questions are a favorite in coding interviews because they look simple, hide several edge cases, and reveal quickly whether a candidate sorts first and thinks second. Almost every interval problem uses one of three ideas: sort by start, sweep with a pointer, or track active intervals with a heap. Learn those and the family becomes predictable. The core move: sort by start time For Merge Intervals, sort by start, then walk the list. Keep the last merged interval; if the current start is less than or equal to its end, extend the end to the maximum of both ends. Otherwise push a new interval. Sorting costs O(n log n), the sweep O(n). Two details interviewers check: you take max of the ends (a short interval can sit inside a long one), and you decide whether touching intervals like [1,2] and [2,3] count as overlapping. Ask that question out loud before coding. Insert Interval: three phases When the list is already sorted and non-overlapping, you do not need to re-sort. Copy every interval that ends before the new one starts, merge every interval that overlaps the new one by widening its start and end, then copy the rest. Describing it as three phases makes the code easy to follow and easy to test. Counting overlaps: Meeting Rooms "Can one person attend all meetings?" is just sort and check whether any start is before the previous end. "How many rooms are needed?" is the more interesting version. Two clean solutions: - Min-heap of end times: sort by start; for each meeting, pop the heap while the earliest end is less than or equal to the current start, push the current end, and track the maximum heap size. - Sweep line: put all starts in one sorted array and all ends in another, move two pointers, increment on a start, decrement on an end. This is O(n log n) and avoids a heap entirely. Mentioning both and explaining the trade-off is an easy way to show depth. Removing overlaps: greedy by end time Non-overlapping Intervals (minimum removals) flips the sort key: sort by end, keep the interval that finishes earliest, and count every interval that starts before the kept end. The reason is the classic activity-selection argument: finishing early leaves the most room for later intervals. If you can explain that proof in one or two sentences, interviewers notice. Edge cases to say before you test - Empty input or a single interval. - Intervals given unsorted, or with start greater than end. - Fully nested intervals. - Identical intervals and touching endpoints. - Very large coordinates, where using a difference array would waste memory. A short practice plan Solve, in order: Merge Intervals, Insert Interval, Meeting Rooms, Meeting Rooms II, Non-overlapping Intervals, Minimum Number of Arrows to Burst Balloons, and Interval List Intersections. After each one, write down which of the three ideas it used. By the end, new interval problems usually reduce to one you have seen. Communicating while you code Draw the intervals on a number line before writing anything; it makes overlaps obvious to you and the interviewer. If you tend to lose structure when the clock is running, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, which can help you keep your approach organized. Interval problems reward a calm, systematic approach: clarify the overlap rule, choose the sort key deliberately, and test the edge cases out loud.