[每天一道 Leetcode 求组队] 56. 合并区间
Acceml · Acceml · 2018-08-29 20:12:39 +08:00 · 6978 次点击这是一个创建于 2276 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
题解
这个题的基本思路就是当两个区间有重合的时候,第一个区间的 end >= 第二个区间的 start。前提是我们都是从小到大排好序的。那么合并完的区间就是[第一个区间的 start, 第二个区间的 end]。遍历结束,即可得到最终的解。
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
// sort start&end
int n = intervals.size();
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals.get(i).start;
ends[i] = intervals.get(i).end;
}
Arrays.sort(starts);
Arrays.sort(ends);
// loop through
int i = 0;
List<Interval> res = new ArrayList<>();
while (i < n) {
int st = starts[i];
while (i < n - 1 && starts[i + 1] <= ends[i]) i++;
int en = ends[i];
res.add(new Interval(st, en));
i++;
}
return res;
}
}
热门阅读
最近在刷题，有一起的可以加手撕代码群：805423079
 |
1
ihainan 2018-08-29 20:32:59 +08:00
[第一个区间的 start, 第二个区间的 end] 这是错的，应该是 [第一个区间的 start, 区间最大的 end]，举例：[1, 4], [2, 3]。
|
 |
3
wind3110991 2018-08-30 10:36:25 +08:00
def merge(region_list):
total_region = [] if not test_list: return [] for region in region_list: if not total_region: total_region = region_list[0] continue # min if total_region[0] > region[0]: total_region[0] = region[0] # max if total_region[1] < region[1]: total_region[1] = region[1] return total_region test_list = [[1,3],[2,6],[8,10],[15,18]] test_list2 = [[1,4],[4,5]] l1 = merge(test_list) l2 = merge(test_list2) print l1, l2 |
 |
4
Raisu 2018-08-30 11:10:45 +08:00 via Android
一天一道太小了吧。。。
|
|
6
Raisu 2018-09-12 23:58:39 +08:00
我现在基本一天 3-5 道题，不过都是做的 easy，等做到 100 道以后就准备复习一下算法再做 medium 100 道。不知道到时候面试能过不
|
 |
7
pg633 2018-12-10 10:07:45 +08:00
困难 随便切 ，中等 各种卡
|
Select Language