[LC] 56. Merge Intervals
2024-09-07 07:41:13
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[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].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Solution 1:
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
if (intervals.length == 0) {
return new int[][] {};
}
Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
int start = intervals[0][0];
int end = intervals[0][1];
for (int[] interval: intervals) {
if (interval[0] <= end) {
end = Math.max(end, interval[1]);
} else {
res.add(new int[]{start, end});
start = interval[0];
end = interval[1];
}
}
// need to add back the last tuple
res.add(new int[]{start, end});
return res.toArray(new int[][] {});
}
}
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
return intervals;
}
List<int[]> list = new ArrayList<>();
int[] startArr = new int[intervals.length];
int[] endArr = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
startArr[i] = intervals[i][0];
endArr[i] = intervals[i][1];
}
Arrays.sort(startArr);
Arrays.sort(endArr);
int start = startArr[0];
int end = endArr[0];
for (int i = 1; i < intervals.length; i++) {
if (startArr[i] <= end) {
end = endArr[i];
} else {
list.add(new int[]{start, end});
start = startArr[i];
end = endArr[i];
}
}
list.add(new int[]{start, end});
int[][] res = new int[list.size()][2];
int count = 0;
for (int i = 0; i < list.size(); i++) {
res[i][0] = list.get(i)[0];
res[i][1] = list.get(i)[1];
}
return res;
}
}
Solution 2:
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/ public class Solution {
/**
* @param intervals: interval list.
* @return: A new interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
// write your code here
if (intervals == null || intervals.size() <= 1) {
return intervals;
}
List<Interval> res = new ArrayList<>();
// Collections work on List while Arrays work on array
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}); Interval pre = null;
for (Interval cur: intervals) {
if (pre == null || cur.start > pre.end) {
res.add(cur);
pre = cur;
} else {
pre.end = Math.max(cur.end, pre.end);
}
}
return res;
}
}
最新文章
- (十三) [终篇] 一起学 Unix 环境高级编程 (APUE) 之 网络 IPC：套接字
- 1 TKinter小窗口及标题
- Day4 - Python基础4 迭代器、装饰器、软件开发规范
- cypress的EZ-USB对于USB的介绍
- 【Cocos2d-x】源代码分析之 2d/ui/Widget
- Java日期的格式String类型GMT,GST换算成日期Date种类
- Nagios监控远程主机
- Tesseract-ocr 工具使用记录
- [Swift]LeetCode407. 接雨水 II | Trapping Rain Water II
- Storm介绍及安装部署
- Android平台上的Aplay与TinyAlsa移植使用
- 通过流量清理防御DDoS
- BZOJ1001 BJOI2006狼抓兔子（最小割+最短路）
- 用dlopen，dlsym加载动态链接库.so中函数
- Express使用Https服务器
- P4811 C’s problem(c)
- python,如何获取字符串中的子字符串，部分字符串
- scrapy与redis分布式组件
- 达梦数据库（DaMeng）如何删除IDENTITY自增属性字段
- Zabbix——解决中文显示乱码