Merge Interval leetcode java

题目:

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].

 

题解:

这道题主要难点是改写Comparator。

 Comparator接口定义了两个方法:compare( )和equals( )。这里给出的compare( )方法按顺序比较了两个元素:
  
  int compare(Object obj1, Object obj2)
  
   obj1和obj2是被比较的两个对象。当两个对象相等时,该方法返回0;当obj1大于obj2时,返回一个正值;否则,返回一个负值。如果用于比较 的对象的类型不兼容的话,该方法引发一个ClassCastException异常。通过覆盖compare( ),可以改变对象排序的方式。例如,通过创建一个颠倒比较输出的比较函数,可以实现按逆向排序。
  
  这里给出的equals( )方法,测试一个对象是否与调用比较函数相等:
  
  boolean equals(Object obj)
  
  obj是被用来进行相等测试的对象。如果obj和调用对象都是Comparator的对象并且使用相同的排序。该方法返回true.否则返回false.重载equals( )方法是没有必要的,大多数简单的比较函数都不这样做。

 

具体代码如下:

 1     public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
 2         if (intervals == null || intervals.size() <= 1)
 3             return intervals;
 4  
 5         // sort intervals by using self-defined Comparator
 6         Collections.sort(intervals, new IntervalComparator());
 7  
 8         ArrayList<Interval> result = new ArrayList<Interval>();
 9  
10         Interval prev = intervals.get(0);
11         for (int i = 1; i < intervals.size(); i++) {
12             Interval curr = intervals.get(i);
13  
14             if (prev.end >= curr.start) {
15                 // merged case
16                 Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
17                 prev = merged;
18             } else {
19                 result.add(prev);
20                 prev = curr;
21             }
22         }
23  
24         result.add(prev);
25  
26         return result;
27         }
28     }
29  
30     class IntervalComparator implements Comparator<Interval> {
31         public int compare(Interval i1, Interval i2) {
32             return i1.start - i2.start;
33         }

 Refrence:

 http://www.programcreek.com/2012/12/leetcode-merge-intervals/

 http://www.blogjava.net/yesjoy/articles/126046.html

Merge Interval leetcode java,布布扣,bubuko.com

Merge Interval leetcode java

上一篇:C++ String类字符串操作


下一篇:python with原理