【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 条评论
登录 后参与评论

相关文章

来自专栏静默虚空的博客

[算法题] 大数减法运算

//test.h #ifndef _TEST_H #define _TEST_H #include <stdlib.h> #define MAXSIZE 50...

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

Scalaz(14)- Monad:函数组合-Kleisli to Reader

  Monad Reader就是一种函数的组合。在scalaz里函数(function)本身就是Monad,自然也就是Functor和applicative。我...

1685
来自专栏Java Edge

Java Map的containsKey(Object key)和containsValue(Object value)方法

2807
来自专栏颇忒脱的技术博客

Mybatis Mapper.xml继承机制

Mybatis实际上隐藏了一个功能:Mapper.xml可以继承,这个在官方文档中并没有提到过,不过在这个issue (commit)里提到过。

723
来自专栏恰同学骚年

.NET中那些所谓的新语法之三:系统预定义委托与Lambda表达式

开篇:在上一篇中,我们了解了匿名类、匿名方法与扩展方法等所谓的新语法,这一篇我们继续征程,看看系统预定义委托(Action/Func/Predicate)和超爱...

893
来自专栏码匠的流水账

聊聊flink的ParallelIteratorInputFormat

本文主要研究一下flink的ParallelIteratorInputFormat

553
来自专栏跟着阿笨一起玩NET

DBNull.Value与Null的区别

Null是.net中无效的对象引用。 DBNull是一个类。DBNull.Value是它唯一的实例。它指数据库中数据为空(<NULL>)时,在.net中的值。 ...

491
来自专栏CodingToDie

FastSql ORM 实现

FastSql 中 ORM 的实现 Table of Contents 原理 实现 1. 使用注解 2. 反射工具类 3. 简单的 model 4. 注解解析 ...

4286
来自专栏kevindroid

LeetCode3. Longest Substring Without Repeating Characters

1353
来自专栏数据库

MySQL数据库应用总结(八)—MySQL数据库的数据类型和运算符(下)

SQL语法预览: 创建表字段数据类型:【createtable 表名(字段名称 数据类型); 】 插入字段值:【insert into表名 values(值1,...

19310

扫码关注云+社区