Intervals

Almost always: sort first. By start to merge, by end to select greedily.

Trigger in the prompt: 'Intervals', 'meetings', 'scheduling', 'overlapping'.

mediumInsert Interval

Insert a new interval into a sorted, non-overlapping list, merging as needed.

Trigger

'Insert into a sorted interval list'.

Approach
  1. Three phases, in order: intervals entirely before the new one, intervals overlapping it, intervals entirely after.
  2. Phase two merges by taking min of starts and max of ends.
  3. The input is already sorted, so no sort is needed — that is the whole reason this is O(n).
Target complexity

O(n) time, O(n) space for the output.

Pitfall

Re-sorting the input. It is already sorted, and sorting throws away the linear bound.

Say it out loud

“The list is already sorted, so I can do it in one linear pass with three phases: copy what ends before the new interval, merge everything that overlaps, then copy the rest. No sort needed, so it's linear rather than n log n.”

Solve on LeetCode
mediumMerge Intervals

Merge all overlapping intervals in a list.

Trigger

'Intervals', 'overlapping', 'merge'.

Approach
  1. Sort by start — that is the move that makes everything else linear.
  2. Sweep: if the current interval starts before the last one ends, extend the end; otherwise append.
  3. Ask whether touching intervals ([1,2] and [2,3]) count as overlapping.
Target complexity

O(n log n) from the sort, O(n) space for the output.

Pitfall

Extending with `end = current.end` instead of `max(end, current.end)`. A fully contained interval then shrinks the result.

Say it out loud

“Sorting by start is what turns this into a single sweep. Then it's one comparison per interval. The one detail is taking the max when I extend — an interval fully inside the previous one would otherwise shrink the merged range.”

Solve on LeetCode
mediumNon-overlapping Intervals

Remove the fewest intervals so that the rest do not overlap.

Trigger

'Remove the minimum', 'maximum non-overlapping set' — activity selection.

Approach
  1. Reframe as maximisation: keep as many as possible, remove the rest.
  2. Greedy sorted by **end time**, not by start. Always keep the one that finishes earliest.
  3. Justify with an exchange argument: finishing earlier never leaves fewer options.
Target complexity

O(n log n) from the sort, O(1) extra space.

Pitfall

Sorting by start. It gives the wrong answer — one long early interval blocks several short ones.

Say it out loud

“This is activity selection. The counterintuitive part is sorting by end time rather than start: keeping the interval that finishes earliest leaves the most room for the rest. The exchange argument is that swapping any chosen interval for one finishing earlier never hurts.”

Solve on LeetCode