在實際編程面試和算法競賽中重疊問題是一個高頻出現(xiàn)的經(jīng)典題型。它并非指某個特定的算法而是一類問題的集合其核心在于處理多個區(qū)間、線段、時間窗口或集合在數(shù)軸上的相互關(guān)系。很多開發(fā)者初次遇到這類問題時會嘗試用復(fù)雜的多重循環(huán)或條件判斷去模擬結(jié)果代碼冗長且容易出錯。真正高效解決重疊問題的關(guān)鍵在于理解其數(shù)學(xué)模型并掌握幾種核心的處理范式。本文將從零開始帶你理解重疊問題的本質(zhì)。我們會先建立清晰的數(shù)學(xué)模型然后學(xué)習(xí)兩種最核心的解法排序端點法和差分?jǐn)?shù)組法。接著我們會通過多個具體場景如會議室安排、日程合并、任務(wù)調(diào)度的代碼實現(xiàn)將理論轉(zhuǎn)化為可運行的解決方案。最后我們會深入探討邊界條件、性能優(yōu)化以及在實際工程中如數(shù)據(jù)庫查詢優(yōu)化、系統(tǒng)設(shè)計的應(yīng)用思路。無論你是正在準(zhǔn)備技術(shù)面試還是希望在項目中更優(yōu)雅地處理類似邏輯這篇文章都將提供一條從理解到實戰(zhàn)的清晰路徑。1. 理解重疊問題的本質(zhì)與數(shù)學(xué)模型在開始編碼之前我們必須先拋開具體的“會議室”、“日程”等業(yè)務(wù)外殼抽象出重疊問題的統(tǒng)一數(shù)學(xué)模型。這能幫助我們在遇到新場景時快速識別并套用已知的解決方案。1.1 什么是“重疊”在最簡單的二維平面上我們可以用一條數(shù)軸通常是時間軸或位置軸來思考。每個待處理的對象如一個會議、一項任務(wù)、一段路程都可以表示為一個區(qū)間[start, end)。這里采用左閉右開是一種常見且不易出錯的約定它意味著區(qū)間包含起點但不包含終點。例如會議從9點開到10點可以表示為[9, 10)。兩個區(qū)間[s1, e1)和[s2, e2)發(fā)生“重疊”或“沖突”的條件是它們有公共的部分。用數(shù)學(xué)語言描述即max(s1, s2) min(e1, e2)。如果這個不等式成立說明兩個區(qū)間在數(shù)軸上的投影有交集它們重疊了。注意判斷條件不能寫成s1 e2 s2 e1嗎可以但這正是左閉右開區(qū)間的一個精妙之處。對于[s1, e1)和[s2, e2)s1 e2 s2 e1等價于max(s1, s2) min(e1, e2)。使用左閉右開可以避免處理“端點恰好相等時是否算重疊”的邊界爭議。例如一個會議在10點結(jié)束另一個在10點開始[9,10)和[10,11)就不重疊因為max(9,10)10min(10,11)1010 10不成立。1.2 重疊問題的常見變體雖然核心模型一致但根據(jù)問題目標(biāo)的不同我們可以將重疊問題分為幾個典型變體檢測是否存在重疊給定一組區(qū)間判斷其中是否存在任意兩個區(qū)間重疊。尋找最大重疊數(shù)最大并行度給定一組區(qū)間找到同一時刻重疊區(qū)間數(shù)量的最大值。例如需要多少間會議室才能容納所有會議。合并所有重疊區(qū)間將一組區(qū)間中所有相互重疊的區(qū)間合并成一個更大的區(qū)間。在重疊區(qū)間中插入新區(qū)間給定一組已排序且不重疊的區(qū)間插入一個新的區(qū)間必要時合并并返回新的不重疊區(qū)間列表。移除最小區(qū)間數(shù)以消除所有重疊通過移除最少數(shù)量的區(qū)間使得剩下的區(qū)間互不重疊。理解這些變體之間的區(qū)別至關(guān)重要因為它們決定了我們選擇哪種算法作為切入點。1.3 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)區(qū)間表示在代碼中我們?nèi)绾伪硎疽粋€區(qū)間通常有兩種方式使用長度為2的數(shù)組int[] interval {start, end};。簡潔但在傳遞時缺乏語義。定義簡單的區(qū)間類包含start和end兩個屬性。更清晰易于理解和維護。// 方式一使用數(shù)組以Java為例 int[][] intervals {{1, 3}, {2, 6}, {8, 10}}; // 方式二定義類 class Interval { int start; int end; Interval(int s, int e) { start s; end e; } } // 或者使用記錄類Java 14 record Interval(int start, int end) {}在本文的示例中為了清晰起見我們將主要使用類或記錄類來表示區(qū)間。2. 核心解法一排序端點法Sweep Line這是解決重疊問題最通用、最強大的方法尤其擅長解決“最大重疊數(shù)”和“檢測重疊”問題。它的思想是將每個區(qū)間的開始和結(jié)束都看作是數(shù)軸上的“事件點”然后按時間順序掃描這些點通過計數(shù)來動態(tài)計算重疊數(shù)量。2.1 算法步驟與原理假設(shè)我們有一組會議時間[[0,30], [5,10], [15,20]]。事件化將每個區(qū)間拆分成兩個事件。(start, 1)表示一個會議開始重疊數(shù)1。(end, -1)表示一個會議結(jié)束重疊數(shù)-1。對于[0,30]-(0, 1),(30, -1)對于[5,10]-(5, 1),(10, -1)對于[15,20]-(15, 1),(20, -1)排序?qū)⑺惺录c按照時間戳升序排序。如果時間戳相同必須優(yōu)先處理結(jié)束事件-1再處理開始事件1。這是為了保證在同一個時間點先離開的會議不計入重疊。排序后的事件列表為(0,1), (5,1), (10,-1), (15,1), (20,-1), (30,-1)掃描與計數(shù)初始化當(dāng)前重疊數(shù)count 0最大重疊數(shù)maxCount 0。從左到右掃描每個事件遇到(0,1)count 1,maxCount max(0,1)1遇到(5,1)count 2,maxCount max(1,2)2遇到(10,-1)count 1,maxCount保持 2遇到(15,1)count 2,maxCount保持 2遇到(20,-1)count 1,maxCount保持 2遇到(30,-1)count 0掃描結(jié)束最大重疊數(shù)為2。2.2 代碼實現(xiàn)會議室 IILeetCode 上的“會議室 II”是應(yīng)用此方法的經(jīng)典題目。題目描述給你一個會議時間安排的數(shù)組intervals每個會議時間包括開始時間start和結(jié)束時間end返回所需會議室的最小數(shù)量。import java.util.*; public class MeetingRoomsII { public int minMeetingRooms(int[][] intervals) { if (intervals null || intervals.length 0) { return 0; } // 1. 創(chuàng)建事件列表 Listint[] events new ArrayList(); for (int[] interval : intervals) { // 開始事件權(quán)重為1 events.add(new int[]{interval[0], 1}); // 結(jié)束事件權(quán)重為-1 // 注意結(jié)束時間點會議室被釋放所以用-1 events.add(new int[]{interval[1], -1}); } // 2. 排序按時間升序時間相同時結(jié)束事件(-1)在前開始事件(1)在后 events.sort((a, b) - { if (a[0] ! b[0]) { return a[0] - b[0]; // 時間不同按時間排序 } return a[1] - b[1]; // 時間相同按權(quán)重排序-1 1 }); // 3. 掃描 int count 0; int maxCount 0; for (int[] event : events) { count event[1]; // 根據(jù)事件類型更新當(dāng)前會議室使用數(shù) maxCount Math.max(maxCount, count); // 更新峰值 } return maxCount; } // 測試代碼 public static void main(String[] args) { MeetingRoomsII solver new MeetingRoomsII(); int[][] meetings1 {{0, 30}, {5, 10}, {15, 20}}; System.out.println(solver.minMeetingRooms(meetings1)); // 輸出: 2 int[][] meetings2 {{7, 10}, {2, 4}}; System.out.println(solver.minMeetingRooms(meetings2)); // 輸出: 1 } }關(guān)鍵點解釋事件排序規(guī)則a[1] - b[1]確保了當(dāng)時間相同時-1結(jié)束排在1開始前面。這意味著在時間點t我們先讓會議結(jié)束釋放房間再安排新的會議這樣計算出的maxCount才是真正需要的房間數(shù)。時間復(fù)雜度O(N log N)其中 N 是區(qū)間數(shù)量。主要開銷在于排序?？臻g復(fù)雜度O(N)用于存儲事件列表。2.3 排序端點法的優(yōu)勢與局限優(yōu)勢概念清晰將問題轉(zhuǎn)化為事件流符合直覺。通用性強稍加修改即可解決“合并區(qū)間”、“插入?yún)^(qū)間”等問題。易于處理復(fù)雜場景例如如果每個會議有優(yōu)先級或權(quán)重可以將1/-1替換為相應(yīng)的權(quán)重值。局限當(dāng)只需要判斷“是否存在重疊”時有更簡單的方法排序后比較相鄰區(qū)間。如果區(qū)間數(shù)量極大如百萬級且值域范圍有限如一天內(nèi)的秒數(shù)差分?jǐn)?shù)組法可能更高效。3. 核心解法二差分?jǐn)?shù)組法差分?jǐn)?shù)組法適用于值域范圍已知且不大的場景例如一天有86400秒。它的思想是在一條初始全為0的軸上在每個區(qū)間覆蓋的范圍內(nèi)進行“批量加減”操作最后通過前綴和還原出每個點的值這個值就是該點的重疊數(shù)。3.1 算法步驟與原理假設(shè)我們處理一天0-24時的會議時間精度到小時。區(qū)間為[[9,12), [10,15), [14,18)]。初始化差分?jǐn)?shù)組創(chuàng)建一個長度為maxTime 2的數(shù)組diff2是為了方便處理邊界通常maxTime是可能的最大結(jié)束時間所有元素初始化為0。這里maxTime24數(shù)組長度26。區(qū)間操作遍歷每個區(qū)間[start, end)。diff[start] 1表示從start時刻開始重疊數(shù)增加1diff[end] - 1表示到end時刻重疊數(shù)減少1對于[9,12)diff[9],diff[12]--對于[10,15)diff[10],diff[15]--對于[14,18)diff[14],diff[18]--前綴和還原計算差分?jǐn)?shù)組的前綴和prefixSum[i] prefixSum[i-1] diff[i]。prefixSum[i]的值就代表了i時刻的重疊會議數(shù)量。prefixSum[9] 1prefixSum[10] 112prefixSum[11] 2(因為diff[11]0)prefixSum[12] 2-11(遇到diff[12]--)prefixSum[13] 1prefixSum[14] 112prefixSum[15] 2-11... 以此類推 掃描整個prefixSum數(shù)組最大值2就是所需的最大會議室數(shù)。3.2 代碼實現(xiàn)public class MeetingRoomsIIDiffArray { public int minMeetingRooms(int[][] intervals) { // 假設(shè)我們知道時間范圍例如 0 到 1000000 // 如果不知道可以先遍歷一次找到最大結(jié)束時間 int maxEnd 0; for (int[] interval : intervals) { maxEnd Math.max(maxEnd, interval[1]); } // 差分?jǐn)?shù)組長度設(shè)為 maxEnd1 足夠 int[] diff new int[maxEnd 1]; // 1. 進行差分操作 for (int[] interval : intervals) { int start interval[0]; int end interval[1]; diff[start] 1; // 確保 end 索引有效 if (end diff.length) { diff[end] - 1; } } // 2. 計算前綴和并找出最大值 int count 0; int maxCount 0; for (int i 0; i diff.length; i) { count diff[i]; maxCount Math.max(maxCount, count); } return maxCount; } // 測試 public static void main(String[] args) { MeetingRoomsIIDiffArray solver new MeetingRoomsIIDiffArray(); int[][] meetings {{9, 12}, {10, 15}, {14, 18}}; System.out.println(solver.minMeetingRooms(meetings)); // 輸出: 2 } }3.3 差分?jǐn)?shù)組法的優(yōu)勢與局限優(yōu)勢時間復(fù)雜度優(yōu)秀如果值域范圍M可接受時間復(fù)雜度為 O(N M)在 N 很大且 M 相對較小時可能比 O(N log N) 的排序法更快。代碼簡潔邏輯直白就是兩次遍歷。局限空間消耗需要開辟與值域大小相關(guān)的數(shù)組如果值域很大例如時間戳范圍是整個Integer則空間消耗巨大不適用。離散化如果值域大但數(shù)據(jù)點稀疏可以先對所有的start和end進行離散化處理將原始坐標(biāo)映射到緊湊的索引上然后再使用差分?jǐn)?shù)組。但這增加了實現(xiàn)的復(fù)雜度。4. 其他經(jīng)典重疊問題實戰(zhàn)掌握了兩種核心思想后我們來看幾個變體問題的解法。4.1 合并重疊區(qū)間問題以數(shù)組intervals表示若干個區(qū)間的集合其中單個區(qū)間為intervals[i] [start_i, end_i]。請你合并所有重疊的區(qū)間并返回一個不重疊的區(qū)間數(shù)組。思路將所有區(qū)間按照起始時間升序排序。初始化一個結(jié)果列表放入第一個區(qū)間。從第二個區(qū)間開始遍歷如果當(dāng)前區(qū)間的起始時間小于等于結(jié)果列表中最后一個區(qū)間的結(jié)束時間說明它們重疊。此時需要合并即更新結(jié)果列表最后一個區(qū)間的結(jié)束時間為max(當(dāng)前區(qū)間結(jié)束時間 最后一個區(qū)間結(jié)束時間)。否則說明不重疊直接將當(dāng)前區(qū)間加入結(jié)果列表。import java.util.*; public class MergeIntervals { public int[][] merge(int[][] intervals) { if (intervals.length 1) { return intervals; } // 1. 按起始時間排序 Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); Listint[] merged new ArrayList(); // 2. 將第一個區(qū)間加入結(jié)果 merged.add(intervals[0]); for (int i 1; i intervals.length; i) { int[] currentInterval intervals[i]; int[] lastMergedInterval merged.get(merged.size() - 1); // 3. 判斷是否重疊當(dāng)前區(qū)間的開始 上一個合并區(qū)間的結(jié)束 if (currentInterval[0] lastMergedInterval[1]) { // 重疊合并。結(jié)束時間取兩者最大值 lastMergedInterval[1] Math.max(lastMergedInterval[1], currentInterval[1]); } else { // 不重疊直接添加 merged.add(currentInterval); } } return merged.toArray(new int[merged.size()][]); } // 測試 public static void main(String[] args) { MergeIntervals solver new MergeIntervals(); int[][] intervals {{1, 3}, {2, 6}, {8, 10}, {15, 18}}; int[][] result solver.merge(intervals); for (int[] interval : result) { System.out.println(Arrays.toString(interval)); } // 輸出: [1, 6] 和 [8, 10] 和 [15, 18] } }關(guān)鍵點排序后重疊的區(qū)間一定會相鄰。合并時結(jié)束時間要取最大值因為可能存在包含關(guān)系例如[1,5]和[2,3]。4.2 插入?yún)^(qū)間問題給你一個無重疊的、按照區(qū)間起始端點排序的區(qū)間列表intervals和一個新區(qū)間newInterval。你需要確保列表仍然有序且不重疊必要時合并區(qū)間。思路因為原列表已排序且無重疊我們可以分三步走將所有結(jié)束時間小于新區(qū)間開始時間的區(qū)間完全在左邊的直接加入結(jié)果。處理與新區(qū)間重疊的所有區(qū)間找到這些區(qū)間中開始時間的最小值作為合并后區(qū)間的開始結(jié)束時間的最大值作為合并后區(qū)間的結(jié)束。將剩下的區(qū)間完全在右邊的加入結(jié)果。public class InsertInterval { public int[][] insert(int[][] intervals, int[] newInterval) { Listint[] result new ArrayList(); int i 0; int n intervals.length; // 1. 加入所有在新區(qū)間左邊的區(qū)間不重疊 while (i n intervals[i][1] newInterval[0]) { result.add(intervals[i]); i; } // 2. 合并所有與新區(qū)間重疊的區(qū)間 // 初始化合并區(qū)間為新區(qū)間 int mergeStart newInterval[0]; int mergeEnd newInterval[1]; while (i n intervals[i][0] newInterval[1]) { // 重疊條件 mergeStart Math.min(mergeStart, intervals[i][0]); mergeEnd Math.max(mergeEnd, intervals[i][1]); i; } result.add(new int[]{mergeStart, mergeEnd}); // 3. 加入所有在新區(qū)間右邊的區(qū)間不重疊 while (i n) { result.add(intervals[i]); i; } return result.toArray(new int[result.size()][]); } }4.3 無重疊區(qū)間移除最小區(qū)間數(shù)問題給定一個區(qū)間的集合找到需要移除區(qū)間的最小數(shù)量使剩余區(qū)間互不重疊。思路這是一個典型的貪心算法問題。我們可以將其轉(zhuǎn)化為如何選擇最多的不重疊區(qū)間。按照區(qū)間的結(jié)束時間進行升序排序總是選擇結(jié)束時間最早的且不與已選區(qū)間沖突的區(qū)間。這樣能為后面留下更多空間。public class NonOverlappingIntervals { public int eraseOverlapIntervals(int[][] intervals) { if (intervals.length 0) return 0; // 按結(jié)束時間升序排序 Arrays.sort(intervals, (a, b) - Integer.compare(a[1], b[1])); int count 0; // 記錄選擇的不重疊區(qū)間數(shù)量 int end intervals[0][1]; // 第一個被選中的區(qū)間結(jié)束時間 count 1; for (int i 1; i intervals.length; i) { // 如果當(dāng)前區(qū)間開始時間 上一個選中區(qū)間的結(jié)束時間則不沖突可以選中 if (intervals[i][0] end) { count; end intervals[i][1]; // 更新結(jié)束時間 } // 否則當(dāng)前區(qū)間沖突跳過相當(dāng)于移除 } // 需要移除的數(shù)量 總數(shù)量 - 最多能保留的不重疊數(shù)量 return intervals.length - count; } }5. 工程實踐中的常見陷阱與排查在實際項目中應(yīng)用重疊問題算法時以下幾個陷阱需要特別注意。5.1 邊界條件處理邊界條件是重疊問題 Bug 的主要來源。問題場景錯誤處理正確做法空輸入直接開始循環(huán)導(dǎo)致空指針或索引越界。首先判斷 if (intervals null單元素輸入邏輯復(fù)雜化。單元素數(shù)組本身就是結(jié)果無需進入合并或判斷邏輯。端點相等是否算重疊定義模糊代碼邏輯不一致。統(tǒng)一約定。推薦使用左閉右開[start, end)則[1,2)和[2,3)不重疊。在排序端點法中時間相同時讓“結(jié)束事件”先于“開始事件”處理也是基于此約定。大整數(shù)溢出使用int存儲時間戳在計算差值或排序比較時可能溢出。根據(jù)數(shù)據(jù)范圍選擇long。在比較函數(shù)中使用Integer.compare(a, b)或Long.compare(a, b)而非a - b后者可能溢出。5.2 排序比較器的正確寫法在 Java 中為二維數(shù)組或?qū)ο罅斜砼判驎r比較器的寫法至關(guān)重要。// 錯誤寫法可能溢出 Arrays.sort(intervals, (a, b) - a[0] - b[0]); // 正確寫法1使用 Integer.compare Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0])); // 正確寫法2使用 Comparator.comparingInt (Java 8) Arrays.sort(intervals, Comparator.comparingInt(a - a[0]));對于多級排序例如先按開始時間開始時間相同再按結(jié)束時間Arrays.sort(intervals, (a, b) - { if (a[0] ! b[0]) { return Integer.compare(a[0], b[0]); } return Integer.compare(a[1], b[1]); });5.3 性能問題排查當(dāng)區(qū)間數(shù)量巨大例如數(shù)十萬時算法可能成為瓶頸。瓶頸定位使用N表示區(qū)間數(shù)量。排序端點法復(fù)雜度 O(N log N)瓶頸在排序。如果N極大考慮是否能用O(N)的桶排序或基數(shù)排序取決于值域。差分?jǐn)?shù)組法復(fù)雜度 O(N M)M為值域大小。如果M也很大例如全天毫秒數(shù) 86400000空間和時間都可能成為問題。優(yōu)化策略數(shù)據(jù)預(yù)處理如果原始數(shù)據(jù)是字符串如09:00在循環(huán)中反復(fù)解析會極大影響性能。應(yīng)在排序前一次性將所有時間轉(zhuǎn)換為整數(shù)如分鐘數(shù)或秒數(shù)。流式處理如果數(shù)據(jù)來自流如 Kafka無法一次性加載排序可以考慮使用最小堆優(yōu)先隊列。用堆來維護當(dāng)前正在進行的會議結(jié)束時間來動態(tài)計算最大并行度。// 使用最小堆解決“會議室II”的另一種思路 public int minMeetingRoomsWithHeap(int[][] intervals) { if (intervals.length 0) return 0; // 按開始時間排序 Arrays.sort(intervals, (a, b) - a[0] - b[0]); // 最小堆存儲會議的結(jié)束時間 PriorityQueueInteger heap new PriorityQueue(); heap.offer(intervals[0][1]); // 加入第一個會議的結(jié)束時間 for (int i 1; i intervals.length; i) { // 如果當(dāng)前會議的開始時間 堆頂最早結(jié)束的會議的結(jié)束時間 if (intervals[i][0] heap.peek()) { heap.poll(); // 該會議室可以復(fù)用彈出最早結(jié)束的會議 } // 將當(dāng)前會議的結(jié)束時間加入堆可能使用新會議室也可能復(fù)用 heap.offer(intervals[i][1]); } // 堆的大小就是所需會議室的最大數(shù)量 return heap.size(); }離散化對于差分?jǐn)?shù)組法如果值域M很大但數(shù)據(jù)點N相對較少可以對所有出現(xiàn)過的start和end進行排序去重映射到0,1,2,...的索引上然后在壓縮后的坐標(biāo)上進行差分操作最后再將結(jié)果映射回去。這能將復(fù)雜度從 O(NM) 降為 O(N log N)。6. 從算法到工程擴展應(yīng)用與最佳實踐重疊問題的思想遠不止于解決算法題它在軟件工程中有廣泛的應(yīng)用。6.1 數(shù)據(jù)庫查詢優(yōu)化在數(shù)據(jù)庫查詢中經(jīng)常需要判斷時間區(qū)間是否有重疊。例如查詢某個時間段內(nèi)被預(yù)訂的房間。-- 低效查詢可能導(dǎo)致全表掃描和復(fù)雜的索引使用 SELECT * FROM bookings WHERE NOT (end_time input_start OR start_time input_end); -- 高效查詢利用B樹索引對 start_time 或 end_time 進行范圍查詢 -- 重疊條件 start_time input_end AND end_time input_start SELECT * FROM bookings WHERE start_time input_end AND end_time input_start;在表設(shè)計時對start_time和end_time建立復(fù)合索引可以極大提升這類重疊查詢的性能。6.2 系統(tǒng)設(shè)計與資源調(diào)度任務(wù)調(diào)度器在操作系統(tǒng)或分布式任務(wù)調(diào)度平臺如 Airflow, K8s CronJob中需要防止同一資源的任務(wù)在時間上重疊。調(diào)度器內(nèi)部維護一個時間軸使用類似掃描線或最小堆的算法來檢查新任務(wù)是否與已有任務(wù)沖突并決定是排隊、并行執(zhí)行還是拒絕。會議室/資源預(yù)訂系統(tǒng)這是重疊問題的直接應(yīng)用。后端服務(wù)接收到一個預(yù)訂請求[new_start, new_end)時需要快速查詢同一資源在該時間段內(nèi)是否存在已確認(rèn)的預(yù)訂即重疊的區(qū)間。高效的實現(xiàn)是在內(nèi)存或緩存中為每個資源維護一個有序的、不重疊的區(qū)間列表使用平衡二叉搜索樹如 Java 的TreeMap插入新區(qū)間時使用O(log N)的算法進行查找和合并。版本控制與沖突解決在協(xié)同編輯如 Google Docs或分布式版本控制如 Git中當(dāng)多個用戶同時編輯文檔的不同部分時系統(tǒng)需要判斷這些編輯操作可視為對文本區(qū)間的修改是否重疊。重疊的編輯會產(chǎn)生沖突需要解決。6.3 代碼實現(xiàn)的最佳實踐清單防御性編程始終首先檢查輸入有效性null, empty。統(tǒng)一區(qū)間表示在項目內(nèi)部約定使用[start, end)左閉右開表示法并在所有相關(guān)函數(shù)、文檔和注釋中明確說明。封裝區(qū)間邏輯不要將區(qū)間的開始和結(jié)束時間作為兩個孤立的參數(shù)傳遞。定義一個Range或Interval類并將判斷重疊、合并、包含等邏輯封裝為類的方法。選擇合適的數(shù)據(jù)結(jié)構(gòu)需要頻繁插入、刪除和查詢重疊考慮TreeMap或區(qū)間樹。只需要一次性的批量計算排序數(shù)組或列表通常足夠。值域小且固定差分?jǐn)?shù)組是利器。編寫完備的單元測試覆蓋以下場景空輸入、單區(qū)間輸入。完全不相鄰的區(qū)間。首尾相連的區(qū)間根據(jù)約定測試是否重疊。完全包含的區(qū)間。部分重疊的區(qū)間。大數(shù)量級的隨機區(qū)間驗證結(jié)果與簡單暴力算法O(N2)的結(jié)果一致。理解重疊問題的核心在于建立“區(qū)間即數(shù)軸上一段范圍”的幾何直覺并掌握“排序掃描”和“差分前綴和”這兩種降維打擊的武器。在面試中清晰地闡述這兩種方法的原理、時間復(fù)雜度和適用場景比直接背誦代碼更能體現(xiàn)你的功底。在實際工程中根據(jù)數(shù)據(jù)規(guī)模、查詢模式和性能要求靈活選擇或組合這些基礎(chǔ)模式是構(gòu)建健壯、高效系統(tǒng)的關(guān)鍵。下一步你可以嘗試挑戰(zhàn)更復(fù)雜的問題如處理帶權(quán)重的區(qū)間、二維平面上的矩形重疊或是實現(xiàn)一個支持增刪改查的實時區(qū)間管理數(shù)據(jù)結(jié)構(gòu)。