Greedy Algorithms8 sections · 316 units
Open in Course

Merge Intervals - Walkthrough

Tracing the algorithm

Intervals: [[1,3], [2,6], [8,10], [15,18]]. Sorted: [[1,3], [2,6], [8,10], [15,18]]. 1.1. Start result = [[1,3]].

2.2. [2,6]: 22 <= 33? Yes, overlap. Merge to [1, max(3,6)] = [1,6]. Result = [[1,6]].

3.3. [8,10]: 88 <= 66? No. Add new. Result = [[1,6], [8,10]].

4.4. [15,18]: 1515 <= 1010? No. Add new. Result = [[1,6], [8,10], [15,18]]. Notice how we only check against the last merged interval.