這次我們來看一個在編程和算法學習中非常經(jīng)典的問題——重疊問題。這不僅是各類技術(shù)面試中的高頻考點更是實際開發(fā)中處理區(qū)間、時間調(diào)度、資源分配等場景的核心邏輯。很多開發(fā)者面對看似復雜的重疊判斷時容易寫出低效或錯誤的代碼。本文將徹底拆解“重疊問題”的通用解決范式從核心概念、判斷邏輯到多種場景下的應用與優(yōu)化并提供可直接復用的代碼模板。理解重疊問題的關(guān)鍵在于抽象。無論是會議時間沖突、線段區(qū)間相交還是任務資源搶占其本質(zhì)都是判斷兩個或多個“區(qū)間”是否存在公共部分。我們將重點關(guān)注如何用代碼高效、準確地實現(xiàn)這一判斷并探討其在合并區(qū)間、安排無沖突日程、計算最大重疊數(shù)等經(jīng)典算法題目中的應用。文章將提供清晰的判斷公式、多種語言實現(xiàn)、復雜度分析以及針對邊界情況的處理技巧確保讀者看完就能掌握并應用于實際項目。1. 核心能力速覽在深入代碼之前我們先通過一個表格快速把握解決重疊問題的核心要點和所需技能。能力項說明與要求問題本質(zhì)判斷或處理多個“區(qū)間”在數(shù)軸上的相交關(guān)系。區(qū)間通常由起點start和終點end定義。核心判斷兩個區(qū)間 [s1, e1] 和 [s2, e2] 不重疊的條件是e1 s2或e2 s1。反之若條件不成立則重疊。算法基礎需要掌握數(shù)組操作、排序算法。高級應用涉及貪心算法、差分數(shù)組、線段樹等。編程門檻低至中等?；A判斷僅需條件語句處理多個區(qū)間需要排序和遍歷。典型時間復雜度排序 O(n log n) 單次遍歷 O(n)是大多數(shù)區(qū)間問題的標準解法框架。關(guān)鍵考點邊界條件處理區(qū)間是開區(qū)間還是閉區(qū)間起點終點相等算重疊嗎輸出形式布爾值是否重疊、合并后的新區(qū)間列表、需要移除的最小區(qū)間數(shù)、同一時刻最大重疊數(shù)等。適合場景面試刷題LeetCode 系列、日程安排系統(tǒng)、資源沖突檢測、流量合并、版本控制等。2. 適用場景與使用邊界重疊問題的解決方案并非局限于理論它在眾多實際開發(fā)場景中扮演著關(guān)鍵角色。適用場景日程與會議安排這是最直觀的應用。例如開發(fā)一個會議室預訂系統(tǒng)或團隊日歷核心功能就是檢測新的預訂時間段是否與已有預訂重疊。任務調(diào)度與資源分配在操作系統(tǒng)或分布式任務調(diào)度中需要確保在同一時間點同一個CPU核心或同一塊內(nèi)存區(qū)域不會被兩個任務重疊占用。網(wǎng)絡與帶寬管理管理網(wǎng)絡連接的活躍時間段或合并重疊的數(shù)據(jù)流量區(qū)間以優(yōu)化帶寬使用。版本控制與時間線在圖形、視頻編輯或代碼版本管理中處理不同修改版本的有效時間范圍判斷修改是否沖突。幾何計算在游戲開發(fā)、CAD軟件中判斷矩形、立方體等物體在坐標軸上是否發(fā)生碰撞投影到各坐標軸即為區(qū)間重疊問題。使用邊界與注意事項區(qū)間定義必須明確在實現(xiàn)前必須明確區(qū)間是閉區(qū)間[start, end]包含端點開區(qū)間(start, end)還是半開半閉區(qū)間[start, end)。不同的定義會直接影響邊界條件的判斷例如[1,2]和[2,3]在閉區(qū)間定義下重疊于點2在半開區(qū)間[1,2)和[2,3)下則不重疊。本文后續(xù)如無特殊說明默認使用半開半閉區(qū)間[start, end)這是編程中最常見的定義因為它能避免許多邊界麻煩例如一個時刻恰好是另一個區(qū)間的結(jié)束和開始不算沖突。數(shù)據(jù)規(guī)模與性能對于一次性判斷少數(shù)區(qū)間直接雙重循環(huán)比較即可。但當區(qū)間數(shù)量n很大例如數(shù)萬以上且需要頻繁進行沖突檢測或合并時需考慮更高效的數(shù)據(jù)結(jié)構(gòu)如線段樹或區(qū)間樹將查詢復雜度從 O(n) 降至 O(log n)。問題變體基礎是判斷是否重疊。衍生問題包括找出所有重疊的區(qū)間對、合并所有重疊的區(qū)間、計算最少移除多少區(qū)間可使剩余區(qū)間互不重疊、找出同一時刻重疊區(qū)間的最大數(shù)量等。它們基于相同的排序預處理思想但遍歷邏輯不同。3. 環(huán)境準備與前置條件解決重疊問題不依賴特定的外部庫或框架核心是編程語言和邏輯思維。以下是一個通用的環(huán)境準備清單編程語言任選一門你熟悉的語言。本文將使用Python作為示例因其語法簡潔易于表達算法邏輯。同時會提供Java和JavaScript的關(guān)鍵代碼片段以供參考。開發(fā)環(huán)境Python建議使用 Python 3.6。確保已安裝 Python 解釋器。Java需要 JDK 8。JavaScript可在 Node.js 環(huán)境或瀏覽器開發(fā)者工具控制臺中運行。代碼編輯器或 IDE如 VS Code, PyCharm, IntelliJ IDEA 等。測試用例準備準備多組區(qū)間數(shù)據(jù)用于測試應覆蓋以下情況完全不重疊的區(qū)間。完全包含的區(qū)間一個區(qū)間完全在另一個內(nèi)部。部分重疊的區(qū)間。首尾相連的區(qū)間測試邊界條件。單點區(qū)間?？蛰斎牖騿蝹€區(qū)間輸入。4. 核心判斷邏輯與代碼實現(xiàn)一切復雜問題都始于最簡單的單元如何判斷兩個區(qū)間是否重疊。4.1 兩個區(qū)間的重疊判斷我們定義區(qū)間為[start, end)。兩個區(qū)間A[s1, e1)和B[s2, e2)。判斷它們重疊的邏輯是兩個區(qū)間在數(shù)軸上有交集。更直觀的方法是考慮它們什么時候不重疊當 A 完全在 B 的左邊或者 A 完全在 B 的右邊。A 在 B 左邊e1 s2A 在 B 右邊e2 s1因此如果不重疊的條件不滿足那么它們就是重疊的。重疊條件公式def is_overlap(interval1, interval2): # interval [start, end) s1, e1 interval1 s2, e2 interval2 # 如果滿足“不重疊”條件返回 False if e1 s2 or e2 s1: return False # 否則返回 True return True或者更簡潔地def is_overlap(interval1, interval2): s1, e1 interval1 s2, e2 interval2 return not (e1 s2 or e2 s1) # 等價于 return max(s1, s2) min(e1, e2)最后一行return max(s1, s2) min(e1, e2)是另一種經(jīng)典寫法兩個區(qū)間重疊當且僅當它們起點的最大值小于終點的最小值。這個交集就是[max(s1, s2), min(e1, e2))。其他語言實現(xiàn)// Java public boolean isOverlap(int[] interval1, int[] interval2) { int s1 interval1[0], e1 interval1[1]; int s2 interval2[0], e2 interval2[1]; return Math.max(s1, s2) Math.min(e1, e2); // 或者 return !(e1 s2 || e2 s1); }// JavaScript function isOverlap(interval1, interval2) { const [s1, e1] interval1; const [s2, e2] interval2; return Math.max(s1, s2) Math.min(e1, e2); }4.2 多個區(qū)間的重疊判斷與合并這是面試中最常見的問題形式給定一個區(qū)間列表如何高效地處理它們經(jīng)典例題LeetCode 56. 合并區(qū)間以數(shù)組intervals表示若干個區(qū)間的集合其中單個區(qū)間為intervals[i] [start_i, end_i]。請你合并所有重疊的區(qū)間并返回一個不重疊的區(qū)間數(shù)組該數(shù)組需恰好覆蓋輸入中的所有區(qū)間。解題思路貪心算法排序?qū)⑺袇^(qū)間按照起點start進行升序排序。這樣可以保證在遍歷時當前區(qū)間只可能與它后面的區(qū)間重疊簡化了比較邏輯。遍歷與合并初始化一個結(jié)果列表merged放入第一個區(qū)間。然后從第二個區(qū)間開始遍歷取出merged中最后一個區(qū)間last。比較當前區(qū)間curr與last如果curr的起點 last的終點即curr[0] last[1]說明它們重疊。需要合并更新last的終點為max(last[1], curr[1])因為curr可能被last包含也可能延伸出去。如果不重疊則將curr作為一個新區(qū)間加入merged。Python 代碼實現(xiàn)def merge(intervals): :type intervals: List[List[int]] :rtype: List[List[int]] if not intervals: return [] # 1. 按區(qū)間起點排序 intervals.sort(keylambda x: x[0]) merged [] # 2. 遍歷并合并 for interval in intervals: # 如果 merged 為空或者當前區(qū)間與 merged 中最后一個區(qū)間不重疊 if not merged or merged[-1][1] interval[0]: merged.append(interval) else: # 否則有重疊合并區(qū)間更新最后一個區(qū)間的終點 merged[-1][1] max(merged[-1][1], interval[1]) return merged # 測試 test_intervals [[1,3],[2,6],[8,10],[15,18]] print(merge(test_intervals)) # 輸出[[1,6],[8,10],[15,18]]復雜度分析時間復雜度 O(n log n)主要開銷在于排序。之后的一次線性遍歷是 O(n)?？臻g復雜度 O(log n) 或 O(n)排序本身需要 O(log n) 的?？臻g使用語言內(nèi)置的排序算法。結(jié)果列表merged在最壞情況下所有區(qū)間都不重疊需要 O(n) 空間。5. 功能測試與效果驗證掌握了核心算法后我們需要通過一系列測試用例來驗證代碼的健壯性并理解不同問題變體的解法。5.1 測試1基礎合并功能測試目的驗證合并算法能正確處理典型的重疊情況。輸入[[1,3],[2,6],[8,10],[15,18]]操作調(diào)用merge函數(shù)。預期輸出[[1,6],[8,10],[15,18]]判斷成功輸出結(jié)果與預期完全一致且區(qū)間已排序。常見失敗原因合并邏輯錯誤如錯誤地使用了interval[1]而不是max或排序時未按起點排序。5.2 測試2邊界條件與復雜重疊測試目的驗證算法處理包含關(guān)系、首尾相接、單點區(qū)間等邊界情況。輸入1包含[[1,10],[2,5],[3,7]]預期輸出[[1,10]]所有區(qū)間都被最大的區(qū)間包含輸入2首尾相接按半開半閉[[1,2],[2,3],[3,4]]預期輸出[[1,2],[2,3],[3,4]]因為[1,2)和[2,3)不重疊輸入3單點區(qū)間[[1,1],[2,2]]起點等于終點代表一個瞬間預期輸出[[1,1],[2,2]]瞬間通常不與任何其他區(qū)間重疊除非定義改變關(guān)鍵點必須根據(jù)題目要求明確區(qū)間定義。許多題目明確說明[start, end]為閉區(qū)間那么[1,2]和[2,3]就重疊于點2合并后應為[1,3]。我們的默認實現(xiàn)是半開半閉適用于大多數(shù)編程場景。5.3 測試3計算最大重疊數(shù)會議室 II問題變體LeetCode 253. 會議室 II給你一個會議時間安排的數(shù)組每個會議時間包括開始和結(jié)束時間[[s1,e1],[s2,e2],...]請你計算至少需要多少間會議室才能滿足這些會議安排。解題思路差分數(shù)組/掃描線將每個會議的開始時間標記為1需要一個新房間結(jié)束時間標記為-1釋放一個房間。將所有時間點排序注意當時間相同時結(jié)束事件應優(yōu)先于開始事件因為同一時刻結(jié)束的會議先釋放房間新的會議才能使用。按時間順序掃描維護一個當前正在進行的會議數(shù)量count。掃描過程中count的最大值就是所需的最少會議室數(shù)量。Python 代碼實現(xiàn)def minMeetingRooms(intervals): if not intervals: return 0 events [] for start, end in intervals: events.append((start, 1)) # 會議開始需求1 events.append((end, -1)) # 會議結(jié)束需求-1 # 關(guān)鍵排序時間升序時間相同時結(jié)束事件-1排在開始事件1前面 events.sort(keylambda x: (x[0], x[1])) curr_rooms 0 max_rooms 0 for _, change in events: curr_rooms change max_rooms max(max_rooms, curr_rooms) return max_rooms # 測試 meetings [[0,30],[5,10],[15,20]] print(minMeetingRooms(meetings)) # 輸出2 [0,30]單獨一間[5,10]和[15,20]共用一間5.4 測試4無重疊區(qū)間的最小移除量問題變體LeetCode 435. 無重疊區(qū)間給定一個區(qū)間的集合找到需要移除區(qū)間的最小數(shù)量使剩余區(qū)間互不重疊。解題思路貪心算法類似安排最多活動按區(qū)間終點end進行升序排序。優(yōu)先選擇結(jié)束早的區(qū)間可以為后面留下更多空間。遍歷排序后的區(qū)間維護一個“當前已選區(qū)間的結(jié)束時間”end。如果當前區(qū)間的起點當前end說明不沖突可以選擇它并更新end為當前區(qū)間的終點。否則說明沖突這個區(qū)間需要被移除跳過它end不變。最后用總區(qū)間數(shù)減去最多能選出的不重疊區(qū)間數(shù)即為最少需要移除的數(shù)量。Python 代碼實現(xiàn)def eraseOverlapIntervals(intervals): if not intervals: return 0 # 按區(qū)間終點排序 intervals.sort(keylambda x: x[1]) count 0 # 記錄選擇的不重疊區(qū)間數(shù)量 end float(-inf) # 初始化一個極小的結(jié)束時間 for interval in intervals: if interval[0] end: # 當前區(qū)間起點 上一個選擇區(qū)間的終點不沖突 count 1 end interval[1] # 更新結(jié)束時間 # 否則沖突跳過相當于移除 return len(intervals) - count # 總區(qū)間數(shù) - 最多保留數(shù) 最少移除數(shù) # 測試 intervals [[1,2],[2,3],[3,4],[1,3]] print(eraseOverlapIntervals(intervals)) # 輸出1 移除[1,3]6. 接口設計與批量任務處理在實際項目中重疊判斷邏輯通常會被封裝成服務或工具函數(shù)供其他模塊調(diào)用。這里我們設計一個簡單的類并討論批量處理。6.1 設計一個區(qū)間工具類class IntervalUtils: 區(qū)間操作工具類 staticmethod def is_overlap(i1, i2): 判斷兩個區(qū)間是否重疊半開半閉 return max(i1[0], i2[0]) min(i1[1], i2[1]) staticmethod def merge_intervals(intervals): 合并重疊區(qū)間 if not intervals: return [] intervals.sort(keylambda x: x[0]) merged [intervals[0]] for curr in intervals[1:]: last merged[-1] if curr[0] last[1]: # 重疊 last[1] max(last[1], curr[1]) else: merged.append(curr) return merged staticmethod def find_all_overlaps(intervals): 找出所有互相重疊的區(qū)間對暴力法適用于n不大時 n len(intervals) overlaps [] for i in range(n): for j in range(i1, n): if IntervalUtils.is_overlap(intervals[i], intervals[j]): overlaps.append((intervals[i], intervals[j])) return overlaps staticmethod def max_overlap_count(intervals): 計算同一時刻的最大重疊區(qū)間數(shù)掃描線法 events [] for start, end in intervals: events.append((start, 1)) events.append((end, -1)) events.sort(keylambda x: (x[0], x[1])) curr_count 0 max_count 0 for _, change in events: curr_count change max_count max(max_count, curr_count) return max_count # 使用示例 utils IntervalUtils() test_list [[1,3], [2,4], [5,7]] print(utils.merge_intervals(test_list)) # [[1,4],[5,7]] print(utils.max_overlap_count(test_list)) # 2 (在時間點2到3之間[1,3]和[2,4]重疊)6.2 批量任務處理思路當需要處理海量區(qū)間數(shù)據(jù)例如日志時間段分析、海量日程沖突檢測時直接使用 O(n2) 的算法是不可行的?？梢钥紤]以下優(yōu)化排序掃描是基礎對于合并、最大重疊數(shù)等問題O(n log n) 的排序掃描算法已經(jīng)足夠高效。增量處理如果數(shù)據(jù)是流式輸入的可以使用平衡二叉搜索樹如 Python 的sortedcontainers庫中的SortedList來動態(tài)維護區(qū)間集合支持在 O(log n) 時間內(nèi)插入新區(qū)間并判斷是否與現(xiàn)有區(qū)間沖突?？臻g換時間差分數(shù)組如果時間點是離散的且范圍不大例如一天中的分鐘數(shù)可以創(chuàng)建一個差分數(shù)組。對于每個區(qū)間[start, end)執(zhí)行diff[start] 1,diff[end] - 1。然后前綴和的最大值就是最大重疊數(shù)。時間復雜度 O(n T)T 是時間范圍。分布式處理如果數(shù)據(jù)量極大可以將區(qū)間按時間范圍分片在不同的機器上并行執(zhí)行合并或統(tǒng)計操作最后再合并結(jié)果。7. 資源占用與性能觀察重疊問題算法的性能主要受數(shù)據(jù)規(guī)模n區(qū)間數(shù)量影響。時間復雜度兩個區(qū)間判斷O(1)常數(shù)時間。合并區(qū)間/無重疊區(qū)間O(n log n)主導因素是排序。Python 的list.sort()使用 Timsort平均和最壞情況都是 O(n log n)。遍歷是 O(n)。找出所有重疊對暴力O(n2)僅適用于 n 較小如 1000的情況。最大重疊數(shù)掃描線O(n log n)同樣是排序主導?？臻g復雜度除結(jié)果存儲外排序通常需要 O(log n) 的?？臻g遞歸深度。掃描線算法需要 O(n) 空間存儲事件列表。性能觀察點排序是關(guān)鍵確保使用語言內(nèi)置的高效排序函數(shù)。避免不必要的拷貝在合并區(qū)間時直接修改結(jié)果列表的最后一個元素而不是創(chuàng)建新列表。選擇合適的數(shù)據(jù)結(jié)構(gòu)對于需要頻繁插入和查詢的動態(tài)區(qū)間集合考慮使用樹形結(jié)構(gòu)。邊界處理確保區(qū)間比較邏輯正確避免因邊界條件錯誤導致的無限循環(huán)或錯誤結(jié)果。簡單性能測試代碼Pythonimport time, random def generate_intervals(n, max_val1000000): 生成n個隨機區(qū)間 intervals [] for _ in range(n): a random.randint(0, max_val) b random.randint(a, max_val) intervals.append([a, b]) return intervals # 測試不同數(shù)據(jù)規(guī)模下的合并操作耗時 for n in [100, 1000, 10000, 100000]: intervals generate_intervals(n) start time.time() result IntervalUtils.merge_intervals(intervals) end time.time() print(fn{n:6d}, 合并耗時: {(end-start)*1000:.2f} ms, 合并后區(qū)間數(shù): {len(result)})運行上述代碼可以直觀感受算法隨數(shù)據(jù)規(guī)模增長的時間開銷。8. 常見問題與排查方法在實現(xiàn)和應用重疊問題算法時經(jīng)常會遇到一些陷阱。下表列出了常見問題及解決方法。問題現(xiàn)象可能原因排查方式解決方案合并結(jié)果不正確區(qū)間意外丟失或錯誤連接。1. 排序依據(jù)錯誤按終點排序而非起點。2. 合并條件判斷邏輯錯誤如使用而不是。3. 更新合并區(qū)間終點時未取max。打印排序后的區(qū)間列表。單步調(diào)試觀察每次比較和合并的邏輯。用[[1,4],[2,3]]這樣的包含用例測試。確認排序keylambda x: x[0]。確認合并條件為curr[0] last[1]。確認更新操作為last[1] max(last[1], curr[1])。計算最大重疊數(shù)會議室II結(jié)果偏大。事件排序時未正確處理同時發(fā)生的開始和結(jié)束事件。如果開始事件先處理會虛增同一時刻的計數(shù)。打印事件列表(time, delta)并手動模擬掃描過程。確保排序規(guī)則為時間time升序時間相同時結(jié)束事件delta-1優(yōu)先于開始事件delta1。即sort(keylambda x: (x[0], x[1]))。判斷兩個區(qū)間重疊時邊界點處理出錯。對區(qū)間是開區(qū)間、閉區(qū)間還是半開半閉區(qū)間定義不清晰。明確題目或業(yè)務要求的區(qū)間定義。用[1,2]和[2,3]這對邊界用例測試。統(tǒng)一約定在算法領域尤其是編程實現(xiàn)中強烈建議使用半開半閉區(qū)間[start, end)。這樣[1,2)和[2,3)自然不重疊計算長度是end-start不易出錯。如果題目明確為閉區(qū)間則判斷條件應改為max(s1,s2) min(e1,e2)。算法在小數(shù)據(jù)量正確大數(shù)據(jù)量超時。可能使用了 O(n2) 的暴力算法處理“找出所有重疊對”等問題。分析代碼的時間復雜度。檢查是否有雙重循環(huán)遍歷所有區(qū)間對。對于“找出所有重疊對”如果不需要輸出所有對而是計數(shù)或其他聚合信息可考慮掃描線法。如果必須輸出所有對可嘗試先排序再利用一些數(shù)據(jù)結(jié)構(gòu)優(yōu)化但最壞情況仍是 O(n2)。需評估數(shù)據(jù)規(guī)模是否可接受。處理流式數(shù)據(jù)動態(tài)插入?yún)^(qū)間效率低。每次插入都調(diào)用 O(n log n) 的排序和合并。分析數(shù)據(jù)插入和查詢的頻率。使用有序數(shù)據(jù)結(jié)構(gòu)如平衡二叉搜索樹BST或?qū)ｉT維護區(qū)間的數(shù)據(jù)結(jié)構(gòu)如區(qū)間樹。在 Python 中可以借助bisect模塊在有序列表中插入但合并操作仍需 O(n)。對于高性能場景可能需要實現(xiàn)更復雜的數(shù)據(jù)結(jié)構(gòu)。9. 最佳實踐與使用建議始終明確區(qū)間定義在開始編碼前和團隊成員或面試官確認區(qū)間的開閉性。在代碼注釋中明確寫明假設。默認采用[start, end)。先排序后處理對于涉及多個區(qū)間的問題排序通常按起點或終點是打開幾乎所有難題的萬能鑰匙。排序能將亂序的區(qū)間組織成有序序列使得重疊判斷變成相鄰或線性掃描問題。貪心算法的證明對于“最多不重疊區(qū)間”、“最少移除區(qū)間”等問題按終點排序的貪心策略是最優(yōu)的。理解其證明選擇結(jié)束最早的區(qū)間給后續(xù)留下更多空間有助于舉一反三。掃描線法的模板化遇到“最大重疊數(shù)”、“天空線”等問題立刻想到掃描線法。將每個區(qū)間拆分為(位置, 類型)事件排序后掃描是一個強大的模板。編寫單元測試使用多種邊界用例測試你的函數(shù)包括空列表、單區(qū)間、完全不相交的區(qū)間、完全包含的區(qū)間、首尾相接的區(qū)間、負值區(qū)間、大數(shù)值區(qū)間?？紤]溢出和精度如果區(qū)間端點值非常大或是浮點數(shù)注意數(shù)值運算的溢出和精度問題。在比較浮點數(shù)時可能需要考慮一個極小的誤差容忍度epsilon。功能單一化將區(qū)間判斷、合并、最大重疊數(shù)等不同功能封裝成獨立的函數(shù)或類方法提高代碼可讀性和復用性。性能與清晰度的權(quán)衡在大多數(shù)業(yè)務場景和面試中清晰正確的 O(n log n) 解法遠優(yōu)于復雜難懂的 O(n) 解法如果存在。優(yōu)先保證正確性和可讀性。10. 總結(jié)與下一步重疊問題是一個“小而美”的算法范式它用簡潔的排序和掃描邏輯解決了從時間調(diào)度到空間碰撞等一系列實際問題。掌握它不僅意味著你能輕松應對 LeetCode 上相關(guān)的數(shù)十道題目更意味著你擁有了將現(xiàn)實世界中的“沖突檢測”抽象為可計算模型的能力。最值得嘗試的起點無疑是“合并區(qū)間”和“會議室 II”這兩個經(jīng)典問題。它們分別代表了重疊問題的兩大核心處理思路合并與計數(shù)。親手實現(xiàn)它們并用自己的測試用例驗證邊界條件是理解所有變體問題的基礎。最容易踩的坑集中在邊界處理和事件排序上。記住半開半閉區(qū)間的優(yōu)越性記住掃描線法中“結(jié)束先于開始”的排序規(guī)則就能避開 80% 的陷阱。下一步你可以探索更復雜的變體例如插入?yún)^(qū)間LeetCode 57在已排序的無重疊區(qū)間列表中插入一個新區(qū)間并保持結(jié)果無重疊。區(qū)間列表的交集LeetCode 986給定兩個已排序的區(qū)間列表找出它們的交集。刪除被覆蓋區(qū)間LeetCode 1288移除所有被其他區(qū)間完全覆蓋的區(qū)間。將區(qū)間分為最少組LeetCode 2406本質(zhì)是求最大重疊數(shù)。將這些問題的解法融入你的工具箱當你下次需要設計一個預約系統(tǒng)、分析一段日志覆蓋率或處理任何與“范圍”相關(guān)的問題時思路將會清晰得多。建議將本文的核心代碼模板收藏在需要時快速查閱和應用。