首页 > 代码库 > [leetcode] Merge Intervals
[leetcode] Merge Intervals
题目：（Array， Sort）
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].
题解：
引用http://www.cnblogs.com/springfor/p/3872332.html
这道题主要难点是改写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（ ）方法是没有必要的，大多数简单的比较函数都不这样做。
public ArrayList<Interval> merge(ArrayList<Interval> intervals) { if (intervals == null || intervals.size() <= 1) return intervals; // sort intervals by using self-defined Comparator Collections.sort(intervals, new IntervalComparator()); ArrayList<Interval> result = new ArrayList<Interval>(); Interval prev = intervals.get(0); for (int i = 1; i < intervals.size(); i++) { Interval curr = intervals.get(i); if (prev.end >= curr.start) { // merged case Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end)); prev = merged; } else { result.add(prev); prev = curr; } } result.add(prev); return result; } } class IntervalComparator implements Comparator<Interval> { public int compare(Interval i1, Interval i2) { return i1.start - i2.start; }
[leetcode] Merge Intervals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。