首页 > 代码库 > LeetCode: Merge Intervals 解题报告
LeetCode: Merge Intervals 解题报告
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].
SOLUTION 1:
1. 先使用Comparator 的匿名类对intervels进行排序。
2. 把Intervals遍历一次，依次一个一个merge到第1个interval。 把第1个interval设置为last(最后一个加到结果集里）
有2种情况：
（1) cur在last的后面。把last加到结果集，将cur加到结果集中。
(2）cur与last有重合部分，把它们合并，合并之后的区间作为新的last.
所有的都扫完后，把last加到结果集中即可。
注意：因为现在Leetcode所有入参都搞成了List,所以遍历时最好使用Iterator，这样无论对于Linkedlist,还是arraylist，性能都是一样的，否则使用get(i)对于LinkedList会相当的缓慢，就不是O(1)的时间了。
1 /** 2 * Definition for an interval. 3 * public class Interval { 4 * int start; 5 * int end; 6 * Interval() { start = 0; end = 0; } 7 * Interval(int s, int e) { start = s; end = e; } 8 * } 9 */10 public class Solution {11 public List<Interval> merge(List<Interval> intervals) {12 List<Interval> ret = new ArrayList<Interval>();13 if (intervals == null || intervals.size() == 0) {14 return ret;15 }16 17 Collections.sort(intervals, new Comparator<Interval>() {18 public int compare(Interval o1, Interval o2) {19 // sort the intervals by the start.20 return o1.start - o2.start;21 }22 });23 24 // 作为最后一个插入的区间25 Interval last = intervals.get(0);26 27 // 这里要考虑性能。使用iterator的话，对linkedlist会更快. 28 Iterator<Interval> itor = intervals.iterator();29 while (itor.hasNext()) {30 Interval cur = itor.next();31 // cur 在last的右边32 if (cur.start > last.end) {33 // 将cur作为新的last.34 ret.add(last);35 last = cur;36 // cur与last有重合的部分，合并之 37 } else {38 int s = last.start;39 int e = Math.max(last.end, cur.end);40 last = new Interval(s, e);41 }42 }43 44 // 把最后一个区间加上45 ret.add(last);46 47 return ret;48 }49 }
GITHUB CODE
REF: http://blog.csdn.net/fightforyourdream/article/details/16882295
LeetCode: Merge Intervals 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。