博文中会简要介绍Leetcode P0056题目分析及解题思路。
“Merge Intervals”是一道比较典型的利用排序简化算法复杂度的题目，也蕴含了一定的贪心的思想，但主要还是基本的边界条件判断。
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
首先按照开始时间排序。这样一来我们从前往后遍历，后面的interval的开始时间一定大于等于前面的，从而不用考虑后面开始时间更早的情况。
考虑以下两个边界条件：
merged[1] >= interval[0]，即当前interval的开始时间在当前merged过后的interval的结束时间之前或恰好就是结束时间，此时需要merge，根据结束时间来更新当前merged过后的interval
merged[1] < interval[0]，即当前interval与当前merged过后的interval不重叠，存储merged过后的interval，重新开始新一轮merge
以下是Java的题解代码实现。
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1)
return intervals;
Arrays.sort(intervals, (int[] i1, int[] i2) -> i1[0]-i2[0]);
List<int[]> mergedIntervals = new ArrayList<>();
int[] merged = intervals[0];
for (int[] interval: intervals) {
if (interval[0] <= merged[1]) {
merged[1] = Math.max(merged[1], interval[1]);
}
else {
mergedIntervals.add(merged);
merged = interval;
}
}
mergedIntervals.add(merged);
// Java 8 stream()方法
// return mergedIntervals.stream().toArray(int[][]::new);
return mergedIntervals.toArray(new int[0][0]);
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 0)
return intervals;
// 这里的Lambda表达式形参需要是引用类型，否则会有大量时间损耗在拷贝上
sort(intervals.begin(), intervals.end(),
[](const vector<int> &v1, const vector<int> &v2) -> bool {
return v1[0] < v2[0];
});
vector<vector<int>> merged_intervals;
vector<int> merged = intervals[0];
for (vector<int> interval: intervals) {
if (merged[1] >= interval[0])
merged[1] = max(merged[1], interval[1]);
else {
merged_intervals.push_back(merged);
merged = interval;
}
}
merged_intervals.push_back(merged);
return merged_intervals;
}
};