Description
Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.
The intervals in the given list do not overlap.The intervals in different lists may overlap.
Example
Example1
Input: list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)]
Output: [(1,4),(5,6)]
Explanation:
(1,2),(2,3),(3,4) --> (1,4)
(5,6) --> (5,6)
Example2
Input: list1 = [(1,2),(3,4)] and list2 = [(4,5),(6,7)]
Output: [(1,2),(3,5),(6,7)]
Explanation:
(1,2) --> (1,2)
(3,4),(4,5) --> (3,5)
(6,7) --> (6,7)
Solution
个人觉得，要想一步实现 bug-free，还是有一定难度的，主要需要考虑以下interval 合并情况：
- list1 = [(1,20)], list2 = [(3,10)]，这时候，结果为 [(1,20)]，因为(1,20)会把(3,10)吃掉；
- List1 =[(1,5)], list2 = [(2,6)]，这时候，结果为 [(1,6)]；
- List1 =[(1,5)], list2 = [(2,4)]，这时候，结果为 [(2,5)]。
int p1 = 0;
int p2 = 0;
int index = 0;
public List<Interval> mergeTwoInterval(List<Interval> list1, List<Interval> list2) {
List<Interval> res = new ArrayList(list1.size() + list2.size());
while (p1 < list1.size() && p2 < list2.size()) {
if (list1.get(p1).start < list2.get(p2).start) {
merge(list1, res, 1);
} else {
merge(list2, res, 2);
}
}
while (p1 < list1.size()) {
merge(list1, res, 1);
}
while (p2 < list2.size()) {
merge(list2, res, 2);
}
return res;
}
private void merge(List<Interval> list, List<Interval> res, int colEnum) {
int p = colEnum == 1 ? p1 : p2;
if (index == 0) {
res.add(list.get(p));
index++;
} else {
if (res.get(index - 1).end >= list.get(p).end) {//res 中最后一个节点为(1,6)，当前扫描节点为(4，5)，此时当前扫描节点会被直接无视
//do nothing
} else if (res.get(index - 1).end >= list.get(p).start) {//res 中最后一个节点为(1,6)，当前扫描节点为(4，7)，此时res 中最后一个节点的 end 值会被覆盖为 7。
Interval intervel = res.get(index - 1);
intervel.end = list.get(p).end;
} else {//res 中最后一个节点和当前扫描节点的范围无交集，比如(1,4)和(20,30)
res.add(list.get(p));
index++;
}
}
if (colEnum == 1)
p1++;
else
p2++;
}