leetcode無(wú)重疊區(qū)間怎么使用

本篇內(nèi)容主要講解“l(fā)eetcode無(wú)重疊區(qū)間怎么使用”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“l(fā)eetcode無(wú)重疊區(qū)間怎么使用”吧!

成都創(chuàng)新互聯(lián)是工信部頒發(fā)資質(zhì)IDC服務(wù)器商，為用戶提供優(yōu)質(zhì)的服務(wù)器托管德陽(yáng)服務(wù)

一、題目?jī)?nèi)容

給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意:

可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒(méi)有相互重疊。

示例 1:

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

輸出: 1

解釋: 移除 [1,3] 后，剩下的區(qū)間沒(méi)有重疊。

示例 2:

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

輸出: 2

解釋: 你需要移除兩個(gè) [1,2] 來(lái)使剩下的區(qū)間沒(méi)有重疊。

示例 3:

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

輸出: 0

解釋: 你不需要移除任何區(qū)間，因?yàn)樗鼈円呀?jīng)是無(wú)重疊的了。

二、解題思路

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

2.遍歷區(qū)間，如果區(qū)間末尾小于當(dāng)前的區(qū)間開(kāi)頭，不重疊區(qū)間的長(zhǎng)度加1，更新當(dāng)前的區(qū)間末尾；

3.遍歷結(jié)束，返回原區(qū)間的長(zhǎng)度和不重疊區(qū)間的長(zhǎng)度的差值，即需要移除的區(qū)間長(zhǎng)度；

三、代碼

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


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)

到此，相信大家對(duì)“l(fā)eetcode無(wú)重疊區(qū)間怎么使用”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

網(wǎng)站題目：leetcode無(wú)重疊區(qū)間怎么使用
文章分享：http://muchs.cn/article32/gedosc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、外貿(mào)網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、網(wǎng)站策劃、用戶體驗(yàn)、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)