[LeetCode] 435. Non-overlapping Intervals

轉自LeetCode

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Example 1:

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

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

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

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

<Solution>

想法如下

• 這題和 452. Minimum Number of Arrows to Burst Balloons 可以用同思路來解

• 和 452 題不同點在於，本題是要找出，需要移掉多少個重疊的區間，才能讓所有區間都不重疊

• 一樣先找出不重疊區間有幾個，最後的答案，就會是 nums.length - cnt

code 如下

Java

kotlin