Merge Intervals
LC #435Medium
Non-overlapping Intervals
Merge Intervals
GoogleAmazonMetaProblem
Find the minimum number of intervals you need to remove to make the rest non-overlapping.
arraysortinggreedymerge-intervals
Constraints
- ›1 ≤ n ≤ 10⁵
- ›-5 × 10⁴ ≤ startᵢ < endᵢ ≤ 5 × 10⁴
Example
Input
intervals = [[1,2],[2,3],[3,4],[1,3]]Output
1Why
Remove [1,3]; remaining [1,2],[2,3],[3,4] are non-overlapping