Merge and Intervals

What is this?

Once things are already in order, problems get much easier. Merging two sorted lists is like shuffling two pre-sorted stacks of cards into one, always taking the smaller top card. And once time slots are lined up by start time, you can spot any overlap with a single left-to-right pass instead of comparing every pair.

💡 Fun fact: The "merge" step here is the exact same move at the heart of merge sort, and it powers how databases combine sorted files too big to fit in memory.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Two recurring payoffs of sorted order. First, the merge step from Merge Sort stands on its own: combine two already-sorted sequences with a linear pass — and when one has spare room, fill it from the back to avoid overwriting. Second, once items are sorted by start time, overlaps become a simple left-to-right sweep: anything that begins before the previous one ends is a conflict.

The pattern

When inputs are already sorted, you rarely need to sort again — you walk them in order. Merging two sorted arrays is a two-pointer scan taking the smaller front each step; the only twist for an in-place merge is to write from the largest end backward so you never clobber a value you still need to read. For intervals, sorting by start lines events up on a timeline: scan once, and the moment a new interval's start falls before the running end, you have an overlap. Sorting turns "compare every pair" into "compare each to its neighbour."

The problems

• Merge Sorted Array — merge two sorted arrays into the first, which has trailing space. Walk both from the back, writing the larger element into the tail; O(m+n) time, O(1) extra space, no risk of overwriting unread values.
• Meeting Rooms — given meeting intervals, decide if a person can attend all of them. Sort by start time, then sweep: if any meeting begins before the previous one ends, they overlap and the answer is false. O(n log n) for the sort, O(1) afterward.

Key takeaways

• Merging two sorted runs is linear — the same step that powers Merge Sort.
• Merge in place from the back when the destination has trailing room, so writes never overwrite unread reads.
• Sort intervals by start, then a single sweep detects every overlap by comparing each start to the running end.
• Why it matters: "sort, then sweep" is one of the most reused interview patterns — the foundation for harder interval problems like merging and meeting-rooms-II.

Order: Merge Sorted Array → Meeting Rooms.