博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
156. Merge Intervals【LintCode by java】
阅读量:4843 次
发布时间:2019-06-11

本文共 1672 字,大约阅读时间需要 5 分钟。

Description

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

[                     [  (1, 3),               (1, 6),  (2, 6),      =>       (8, 10),  (8, 10),              (15, 18)  (15, 18)            ]]

Challenge

O(n log n) time and O(1) extra space.

        题意:给定一个集合,里面有若干无序区间,要求将有重叠部分的区间合并。这个题目的示例给的不是很好,这个示例给人的感觉好像这些区间是有序的。有序和无序,用同样的方法做,结果可能不一样,比如我一开始理解成有序,报错如下:

Input

[(2,3),(4,5),(6,7),(8,9),(1,10)]
Output
[(2,3),(4,5),(6,7),(1,10)]
Expected
[(1,10)]
Hint
Review your code and make sure your algorithm is correct. Wrong answer usually caused by typos if your algorithm is correct.
Input test data (one parameter per line.)

        虽然它本来无序,但我们也可以人为地将它根据first值的大小进行排序,可以使用Collections类中的sort方法(查一下API)对List进行排序。排完之后,就可以对集合内的区间进行合并了。合并的方法与此题类似:   

        申请一个新的集合,再用一个循环,将排好序的区间两两比较,如果无需合并,则将前者加入新的集合,后者继续与后面的区间比较合并。代码如下:

1 public class Solution { 2     /** 3      * @param intervals: interval list. 4      * @return: A new interval list. 5      */ 6      //判断两区间是否相交 7     public List
merge(List
intervals) { 8 // write your code here 9 if(intervals.size()==0||intervals.size()==1)10 return intervals;11 List
res=new ArrayList
();12 Collections.sort(intervals,new IntervalCompare());13 Interval last=intervals.get(0);14 for(int i=1;i
{28 public int compare(Interval a,Interval b){29 return a.start-b.start;30 }31 }32 }

如有错误,欢迎批评指正~

 

 

 

转载于:https://www.cnblogs.com/phdeblog/p/9111599.html

你可能感兴趣的文章
多机共享开发证书
查看>>
【线段树】POJ 3667 Hotel 区间合并
查看>>
MongoDB ObjectId
查看>>
Tsung CentOS 操作系统下搭建tsung性能测试环境_Part 2
查看>>
Docker实战(五)之端口映射与容器互联
查看>>
记一次js之button问题
查看>>
初学python类
查看>>
springmvc学习笔记(18)-json数据交互
查看>>
STL容器介绍
查看>>
如何解决定时文章没法正常发布
查看>>
基于Jmeter+maven+Jenkins构建性能自动化测试平台
查看>>
C#属性升级版--自动属性-chapter 3 P34-36
查看>>
IP 数据包分析上
查看>>
整数数组中最大子数组的和
查看>>
CSS图片垂直居中实现方法详解
查看>>
Python3之os模块
查看>>
GMF改变结点颜色
查看>>
页面定制CSS代码
查看>>
mysql严格模式的开启、关闭
查看>>
WP7获取ISolatedStorage指定文件夹下所有子文件夹或者文件数
查看>>