Why it works
- After sorting by start, an interval that starts past the end of the last group is followed only by intervals that start even further right. None of them can reach back into the group, so each group comes in a row.
- So each interval is compared only with the last one in the result: if it starts no later than its end, it joins it; otherwise it opens a new group.
- The end becomes max of the two ends, not just the new end: [10, 11] lies inside [9, 12], and taking its end would cut the interval short.
Complexity
Time O(n log n): the sort; the pass after it is O(n). Memory O(n) for the result, plus what the sort needs.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗