【LeetCode】Merge Intervals

【LeetCode】Merge Intervals

题目

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

分析

先对intervals集合按start从小到大排序,last变量用于保存可能插入到结果集中的元素,遍历每一个集合中的元素,如果符合合并的条件,将last和当前元素合并,并重新赋值给last,此时last仍然具有合并的潜力;如果不符合合并的条件,则将last放入结果集中,并把当前元素赋值给last,成为一个新的潜在具有合并性的元素。

自定义比较类

     //      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;
        }
    }

    public static final Comparator<Interval> BY_START = new ByStart();

    private static class ByStart implements Comparator<Interval> {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.start - o2.start;
        }
    }

主方法

        public List<Interval> merge(List<Interval> intervals) {
        ArrayList<Interval> result = new ArrayList<Interval>();

        if (intervals == null || intervals.size() == 0) {
            return result;
        }

        //按Interval的start对intervals排序
        Collections.sort(intervals, BY_START);

        Interval last = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval temp = intervals.get(i);
            if (canMerge(last, temp)) {
                if (last.end <= temp.end) {
                    last = new Interval(last.start, temp.end);
                }
                //另外一种情况last保持不变
            } else {
                result.add(last);
                last = intervals.get(i);
            }

        }
        result.add(last);
        return result;
    }

    private boolean canMerge(Interval item1, Interval item2) {
        if (item1.end >= item2.start) {
            return true;
        }
        return false;
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3759
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2608
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

8175
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6436
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2782
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

941
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1192
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1182
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

832

扫码关注云+社区