合併 Java 集合中的重疊區間

1. 概述

在本教程中，我們將研究獲取間隔Collection並合併任何重疊的部分。

2. 理解問題

首先，我們來定義什麼是區間。我們將其描述為一對數字，其中第二個數字大於第一個數字。這也可以是日期，但我們在這裡堅持使用整數。例如，間隔可以是 2 -> 7，或 100 -> 200。

我們可以建立一個簡單的 Java 類別來表示一個區間。我們將start作為第一個數字， end作為第二個和更大的數字：

class Interval {
 int start;
 int end;

 // Usual constructor, getters, setters and equals functions

 }

現在，我們想要取得Interval的Collection並合併任何重疊的部分。我們可以將重疊間隔定義為第二個間隔開始後第一個間隔結束的任何位置。例如，如果我們取兩個區間 2 -> 10 和 5 -> 15，我們可以看到它們重疊，合併它們的結果將是 2 -> 15。

3. 演算法

要執行合併，我們需要遵循以下模式的程式碼：

List<Interval> doMerge(List<Interval> intervals) {
 // Sort the intervals based on the start
 intervals.sort((one, two) -> one.start - two.start);

 // Create somewhere to put the merged list, start it off with the earliest starting interval
 ArrayList<Interval> merged = new ArrayList<>();
 merged.add(intervals.get(0));

 // Loop over each interval and merge if start is before the end of the
 // previous interval
 intervals.forEach(interval -> {
 if (merged.get(merged.size() - 1).end > interval.start) {
 merged.get(merged.size() - 1).setEnd(interval.end);
 } else {
 merged.add(interval);
 }
 });

 return merged;
 }

首先，我們定義了一個方法，它接受一個Interval List並傳回相同但已排序的列表。當然，還有其他類型的Collection可以儲存我們的Interval ，但今天我們將使用List 。

我們需要執行的處理的第一步是對Interval Collection進行排序。我們根據Interval'開始進行排序，這樣當我們循環它們時，每個Interval後面都會跟著最有可能與其重疊的一個。

假設我們的Collection是一個List ，我們可以使用List.sort()來執行此動作。但是，如果我們有不同類型的Collection我們就必須使用其他東西。 List.sort()採用Comparator並且就地排序，因此我們不需要重新分配變數。對於我們的Comparator ，我們可以從第一個Interval的開始減去第二個 Interval 的起點。這導致我們的Collection.

接下來，我們需要在某個地方放置合併過程的結果。為此，我們建立了一個名為merged ArrayList 。我們也可以輸入第一個間隔來開始它，因為我們知道它最早開始。

現在是有趣的部分。我們需要循環每個Interval並做兩件事之一。如果Interval在前一個Interval結束之前開始，我們透過將前一個Interval的結束設定為目前Interval的結束來合併它們。或者，如果Interval在前一個Interval結束後開始，我們只需將其新增至Collection.

最後，我們傳回了合併的Interval列表。

4. 實際例子

讓我們透過測試來看看該方法的實際效果。我們可以定義四個要合併的Interval ：

ArrayList<Interval> intervals = new ArrayList<>(Arrays.asList(
 new Interval(2, 5),
 new Interval(13, 20),
 new Interval(11, 15),
 new Interval(1, 3)
 ));

合併後，我們期望結果只有兩個Interval ：

ArrayList<Interval> intervalsMerged = new ArrayList<>(Arrays.asList(
 new Interval(1, 5),
 new Interval(11, 20)
 ));

我們現在可以使用先前建立的方法並確認它按預期工作：

@Test
 void givenIntervals_whenMerging_thenReturnMergedIntervals() {
 MergeOverlappingIntervals merger = new MergeOverlappingIntervals();
 ArrayList<Interval> result = (ArrayList<Interval>) merger.doMerge(intervals);
 assertArrayEquals(intervalsMerged.toArray(), result.toArray());
 }

5. 結論

在本文中，我們學習如何在 Java 中合併Collection中的重疊間隔。我們看到合併間隔的過程相當簡單。首先，我們必須知道如何按起始值對它們進行正確排序。然後我們只需要明白，當一個間隔在前一個間隔結束之前開始時，我們需要合併它們。

與往常一樣，範例的完整程式碼可在 GitHub 上取得。