Zero To DSAZero To DSA
Privacy Policy
Merge IntervalsJump Game

Non-Overlapping Intervals

medium
Time: O(n log n)
Space: O(1)

Given an array of intervals, return the minimum number of intervals to remove to make the rest non-overlapping.

Constraints

  • 1 <= intervals.length <= 10⁵

Examples

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Remove [1,3] to make the rest non-overlapping.
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2