合并区间

题意

给出若干闭合区间,合并所有重叠的部分。

样例

给出若干闭合区间,合并所有重叠的部分。

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

思路

题目没有说是有序的集合,所以我们要进行先根据左端点进行排序,排序后,判断右端点与下一个节点的左端点的大小来决定是否合并区间。

代码实现

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 */

class Solution {
    /**
     * @param intervals, a collection of intervals
     * @return: A new sorted interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> ans = new ArrayList<Interval>();
        
        Collections.sort(intervals, new Comparator<Interval>(){
            @Override
            public int compare(Interval obj1, Interval obj2){
                return obj1.start - obj2.start;
            }
        });
        
        Interval last = null;
        for (Interval item : intervals) {
            if (last == null || last.end < item.start) {
                ans.add(item);
                last = item;
            } else {
                last.end = Math.max(last.end, item.end);
            }
        }
        
        return ans;
    }
}

原题地址

LintCode:合并区间

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青玉伏案

Objective-C中的继承和多态

   面向对象编程之所以成为主流的编程思想和他的继承和多态是分不开的,只要是面向对象语言都支持继承和多态,当然不同的OOP语言之间都有其特点。OC中和Java类...

22380
来自专栏iOS技术杂谈

iOS block探究(一): 基础详解你要知道的block都在这里

你要知道的block都在这里 转载请注明出处 https://cloud.tencent.com/developer/user/1605429 本文大纲 blo...

34180
来自专栏wOw的Android小站

[Objective-C] id类型和instancetype类型

id数据类型可以存储任何类型的对象。可以说,它是一般对象类型。 例如可以声明一个为id类型的变量:

11310
来自专栏猿人谷

OC字符串常用函数

创建一个字符串对象: NSstring * str1 = @"hello"; NSString * str = [[NSString alloc]initWit...

199100
来自专栏数据结构与算法

4927 线段树练习5

时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Description 有n个数和5种操作...

371140
来自专栏互联网杂技

今天由我亲自给大家总结

javascript内置对象有哪些? reg正则,booer,math,string,arr,obj,number,date,function,window全...

34180
来自专栏青玉伏案

Objective-C精选字符串处理方法

        无论是什么编程语言对字符串的操作是少不了的,对复杂的字符串的分析和操作我们可以用正则表达式来达到我们的目的。简单的字符串处理我们可以借助OC中N...

22450
来自专栏函数式编程语言及工具

Scalaz(3)- 基础篇:函数概括化-Generalizing Functions

  Scalaz是个通用的函数式编程组件库。它提供的类型、函数组件都必须具有高度的概括性才能同时支持不同数据类型的操作。可以说,scalaz提供了一整套所有编程...

19290
来自专栏自学笔记

Data Structure_数组_栈_队列_链表_霍夫曼数组栈队列链表哈夫曼

这就表示一个数组,这个数组有八个元素存放。对于元素的获取,主要就是通过下标获取,所以索引对于数组是很重要的,这个索引可以是有意义的,也可以是没有意义的。比如ar...

8220
来自专栏iOS 开发杂谈

iOS 泛型 ObjectType 协变 __covariant 逆变 __contravariant

__covariant(协变):用于泛型数据强转类型,可以向上强转,子类可以转成父类。 __contravariant(逆变):用于泛型数据强转类型,可以向下...

40330

扫码关注云+社区

领取腾讯云代金券