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

思路分析:这题关键要想到先对区间排序,然后从前向后扫描,如果下一个没法合并,就添加一个结果区间;如果可以,还要继续向后看,保存当前的lower bound和upper bound,如果upper bound比下一个区间的上界小(肯定大于等于下一个区间的下界,否则属于无法合并的情况),那么用下一个区间上界更新upper bound。排序时要注意如果start相等,根据end排序。另外还有对于最后一个区间要特殊处理,不然可能出现漏掉最后一个区间的情况。另外这题需要对pair这种结构体排序,可以用Collections的sort方法,需要重写Comparator类的compare方法,然后构造Comparator对象传入sort作为第二个参数,制定排序规则。第一个参数是List对象。Collections的sort方法和Comparator类的compare方法重写非常常用,对于结构体排序的场景非常适合,要熟悉掌握。

AC Code:

/**
 * 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 class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size() <= 1 || intervals == null) return intervals;
        else {
            List<Interval> res = new ArrayList<Interval>();
            Comparator<Interval> comp = new Comparator<Interval>(){
                
                public int compare (Interval i1, Interval i2){
                    if(i1.start == i2.start){
                        return i1.end - i2.end;
                    }
                    return i1.start - i2.start;
                }
            };
            Collections.sort(intervals, comp);
            
            int lb = intervals.get(0).start;
            int ub = intervals.get(0).end;
            int index = 1;
            while(index < intervals.size()){
                Interval cur = intervals.get(index);
                if(ub >= cur.start){
                    if(ub < cur.end) ub = cur.end;
                    
                } else {
                    Interval newInterval = new Interval(lb, ub);
                    res.add(newInterval);
                    lb = cur.start;
                    ub = cur.end;
                }
                //Special case: when the interval is the last interval
                //you need to stop and generated a new interval based 
                //on the current lb and ub
                if(index == intervals.size() - 1){
                    Interval newInterval = new Interval(lb, ub);
                    res.add(newInterval);
                    break;
                }
                index++;
            }
        return res;    
        }
    }
}


LeetCode Merge Intervals