Intervals-Algorithms

#intervals-algorithms

Merge Overlapping Intervals

Problem Statement: Merge Overlapping Intervals

Given an integer array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals. For example \([[1,3],[2,6],[8,10],[15,18]] \to [[1,6],[8,10],[15,18]]\) because \([1,3]\) and \([2,6]\) overlap and merge into \([1,6]\).

Solution: Sort by Start Time and then Linear Scan

Like Minimum Size Subarray Sum , contiguity hints at a linear scan being useful. If we sort intervals by start, then it’s a matter of starting at some intervals[i] and expanding until some intervals[j], \(j > i\) is no longer overlapping.