[435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/) ### 題目描述 Given an array of intervals `intervals` where `intervals[i] = [starti, endi]`, return *the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.* ### 範例 **Example 1:** ``` Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping. ``` **Example 2:** ``` Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping. ``` **Example 3:** ``` Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping. ``` **Constraints**: * 1 <= `intervals.length` <= 10^5^ * `intervals[i].length` == 2 * -5 * 10^4^ <= `starti` < `endi` <= 5 * 10^4^ ### 解答 #### Javascript ```javascript function eraseOverlapIntervals(intervals) { intervals.sort((a, b) => a[1] - b[1]); // 依結束時間排序 let count = 0; let end = intervals[0][1]; for (let i = 1; i < intervals.length; i++) { const [curStart, curEnd] = intervals[i]; if (curStart < end) { count++; } else { end = curEnd; } } return count; } ``` > [name=Marsgoat][time=Jul 19, 2023] #### Python ```python= class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: n = len(intervals) intervals.sort(key=lambda x: x[1]) ans, pre = 0, float('-inf') for start, end in intervals: if start < pre: ans += 1 else: pre = end return ans ``` > [name=Yen-Chi Chen][time=Wed, Jul 19, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)