首页 > 代码库 > 【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].


 

题解:首先对所有的区间按照start大小排序,然后遍历排序后的数组,用last记录前一个区间,如果遍历的当前区间可以和last合并,就把它合并到last里面;否则就把last放到answer list中,并且更新last。

代码如下:

 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     class IntervalComparator implements Comparator<Interval>{12         public int compare(Interval a,Interval b){13             return a.start - b.start;14         }15     }16     public List<Interval> merge(List<Interval> intervals) {17         if(intervals == null || intervals.size() <= 1)18             return intervals;19         Collections.sort(intervals,new IntervalComparator());20         21         ArrayList<Interval> answer = new ArrayList<Interval>();22         23         Interval last = intervals.get(0);24         for(int i = 1;i < intervals.size();i++){25             Interval now = intervals.get(i);26             if(last.end >= now.start){27                 last.end = Math.max(last.end, now.end);28             }29             else{30                 answer.add(last);31                 last = now;32             }33         }34         answer.add(last);35         return answer;36         37          38     }39 }