leetcode無重疊區間怎么使用

本篇內容主要講解“leetcode無重疊區間怎么使用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“leetcode無重疊區間怎么使用”吧!

一、題目內容

給定一個區間的集合，找到需要移除區間的最小數量，使剩余區間互不重疊。

注意:

可以認為區間的終點總是大于它的起點。
區間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3] ]

輸出: 1

解釋: 移除 [1,3] 后，剩下的區間沒有重疊。

示例 2:

輸入: [ [1,2], [1,2], [1,2] ]

輸出: 2

解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊。

示例 3:

輸入: [ [1,2], [2,3] ]

輸出: 0

解釋: 你不需要移除任何區間，因為它們已經是無重疊的了。

二、解題思路

1.按照區間的末尾從小到大排序；

2.遍歷區間，如果區間末尾小于當前的區間開頭，不重疊區間的長度加1，更新當前的區間末尾；

3.遍歷結束，返回原區間的長度和不重疊區間的長度的差值，即需要移除的區間長度；

三、代碼

import sys
class Solution:
    def eraseOverlapIntervals(self, intervals: list) -> int:
        sorted_intervals = sorted(intervals, key=lambda x: x[1])  # 按照區間的末尾從小到大排序
        res = 0  # 不重疊區間的長度
        last = -sys.maxsize  # 區間的末尾
        for i in range(len(sorted_intervals)):
            if last <= sorted_intervals[i][0]:  # 區間末尾小于當前的區間開頭
                res += 1  # 不重疊區間的長度 加1
                last = sorted_intervals[i][1]  # 更新當前的區間末尾
        return len(sorted_intervals) - res  # 需要移除的區間


if __name__ == '__main__':
    s = Solution()
    intervals1 = [[1, 2], [2, 3], [3, 4], [1, 3]]
    ans1 = s.eraseOverlapIntervals(intervals1)
    print(ans1)
    intervals2 = [[1, 2], [1, 2], [1, 2]]
    ans2 = s.eraseOverlapIntervals(intervals2)
    print(ans2)
    intervals3 = [[1, 2], [2, 3]]
    ans3 = s.eraseOverlapIntervals(intervals3)
    print(ans3)

到此，相信大家對“leetcode無重疊區間怎么使用”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！