1. 概述
在这个教程中，我们将探讨如何处理一个包含区间（Interval）的集合，并合并任何重叠的部分。
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) {
intervals.sort(Comparator.comparingInt(interval -> interval.start));
ArrayList<Interval> merged = new ArrayList<>();
merged.add(intervals.get(0));
// < code to merge intervals into merged comes here >
return merged;
}
首先，我们定义了一个方法，它接受一个Interval的List并返回排序后的相同列表。当然，我们的Intervals可以存储在其他类型的Collection中，但今天我们将使用List。
处理过程的第一步是对Interval的Collection进行排序。我们根据Interval的start进行排序，这样当我们遍历它们时，每个Interval后面都是最可能与其重叠的一个。
我们可以使用List.sort()方法来完成这个任务，假设我们的Collection是List。但如果使用的是其他类型的Collection，我们就需要使用其他方法例如。List.sort()方法需要一个Comparator，并且会就地排序，所以我们不需要重新赋值变量。我们使用了Comparator.comparingInt()作为sort()方法的Comparator。
接下来，我们需要一个地方来存放合并过程的结果。为此，我们创建了一个名为merged的ArrayList。我们还可以通过将第一个区间放入其中来初始化它，因为我们知道它的开始时间最早。
现在，我们将将intervals的元素合并到merged中，这是解决方案的主要部分。根据一个interval的start和end，有三种可能性。让我们画一个ASCII图表，以便更容易理解合并逻辑：
-----------------------------------------------------------------------
| Legend: |
| |______| <-- lastMerged - The last lastMerged interval |
| |
| |......| <-- interval - The next interval in the sorted input list |
-----------------------------------------------------------------------
## Case 1: interval.start <= lastMerged.end && interval.end > lastMerged.end
lastMerged.start lastMerged.end
|______________________________|
|...............................|
interval.start interval.end
## Case 2: interval.start <= lastMerged.end && interval.end <= lastMerged.end
lastMerged.start lastMerged.end
|______________________________|
|..................|
interval.start interval.end
## Case 3: interval.start > lastMerged.end
lastMerged.start lastMerged.end
|_________________________|
|..............|
interval.start interval.end
根据ASCII图表，我们在情况1和情况2中检测到了重叠。为了解决这个问题，我们需要合并lastMerged和interval。幸运的是，合并它们是一个直接的过程。我们可以通过选择lastMerged.end和interval.end中的较大值来更新lastMerged.end：
if (interval.start <= lastMerged.end){
lastMerged.setEnd(max(interval.end, lastMerged.end));
}
在情况3中，没有重叠，所以我们将当前的interval作为新元素添加到结果列表merged中：
merged.add(interval);
最后，让我们将合并逻辑实现添加到*doMerge()*方法中，得到完整的解决方案：
List<Interval> doMerge(List<Interval> intervals) {
intervals.sort(Comparator.comparingInt(interval -> interval.start));
ArrayList<Interval> merged = new ArrayList<>();
merged.add(intervals.get(0));
intervals.forEach(interval -> {
Interval lastMerged = merged.get(merged.size() - 1);
if (interval.start <= lastMerged.end){
lastMerged.setEnd(max(interval.end, lastMerged.end));
} else {
merged.add(interval);
}
});
return merged;
}
4. 实践示例
让我们用一个测试来看看这个方法的工作情况。我们可以定义一些想要合并的Intervals：
List<Interval> intervals = new ArrayList<>(Arrays.asList(
new Interval(3, 5),
new Interval(13, 20),
new Interval(11, 15),
new Interval(15, 16),
new Interval(1, 3),
new Interval(4, 5),
new Interval(16, 17)
));
合并后，我们期望结果只有两个Intervals：
List<Interval> intervalsMerged = new ArrayList<>(Arrays.asList(
new Interval(1, 5),
new Interval(11, 20)
));
现在我们可以使用我们之前创建的方法，确认它按预期工作：
MergeOverlappingIntervals merger = new MergeOverlappingIntervals();
List<Interval> result = merger.doMerge(intervals);
assertEquals(intervalsMerged, result);
5. 总结
在这篇文章中，我们学习了如何在Java中合并Collection中的重叠区间。我们看到，合并区间的过程相当简单。首先，我们必须正确地按起始值对其进行排序。然后，我们只需要理解当一个区间开始在前一个区间结束之前时，我们需要合并它们。
如往常一样，这些示例的完整代码可以在GitHub上找到这里。