247. Non-Overlapping Intervals

MediumIntervals

Given an array of intervals `intervals` where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the remaining intervals non-overlapping. Two intervals [a, b] and [c, d] overlap if they share any point in their interior (i.e., a < d and c < b). Intervals that only touch at an endpoint like [1, 2] and [2, 3] do NOT overlap. For example, given intervals = [[1,2],[2,3],[3,4],[1,3]], you need to remove [1,3] to make the rest non-overlapping, so the answer is 1.

Examples

Input: [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Explanation: Remove [1,3] to make the rest non-overlapping: [1,2], [2,3], [3,4].

Constraints

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= start_i < end_i <= 5 * 10^4
Loading...

Run checks all cases above. Submit evaluates all test cases.