Greedy Algorithms8 sections · 316 units
Open in Course

Merge Intervals - Algorithm

Step by step

1.1. Sort intervals by start time.

2.2. Initialize result with the first interval.

3.3. For each remaining interval:

  • If it overlaps with the last interval in result, extend the end.
  • Otherwise, add it as a new interval.

4.4. Return result. Overlap condition: interval.start <= result.last.end. Time: O(nlog⁡n)O(n \log n). Space: O(n)O(n). Common bug: forgetting to take max when merging ends, which loses the longer interval.