题解 | #合并区间#

import java.util.*;
/**
 * 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> results = new ArrayList<>();
        Map<Integer, Integer> mp = new TreeMap<>();
        for (Interval i : intervals) {
            if (!mp.containsKey(i.start)) mp.put(i.start, i.end);
            else {
                if (i.end > mp.get(i.start)) mp.put(i.start, i.end);
            }
        }
        List<List<Integer>> inner_list=new LinkedList<>();
        for (Integer k : mp.keySet()) {
            List<Integer> tmp = new LinkedList<>();
            tmp.add(k);
            tmp.add(mp.get(k));
            inner_list.add(tmp);
        }
        if(inner_list.size()<=0) return results;
        if(inner_list.size()==1){
            Interval inter=new Interval(inner_list.get(0).get(0),inner_list.get(0).get(1));
            results.add(inter);
            return results;

        }
        for(int i=1;i<inner_list.size();i++){
            if(inner_list.get(i).get(0)>inner_list.get(i-1).get(1)){
                Interval interval_tmp=new Interval(inner_list.get(i-1).get(0),inner_list.get(i-1).get(1));continue;
            }
            List<Integer> tmp = new LinkedList<>();
            tmp.add(inner_list.get(i-1).get(0));
            tmp.add(Math.max(inner_list.get(i).get(1),inner_list.get(i-1).get(1)));
            inner_list.set(i-1,tmp);
            inner_list.remove(i);
            i--;
        }
        for(int i=0;i<inner_list.size();i++){
            Interval interval=new Interval(inner_list.get(i).get(0),inner_list.get(i).get(1));
            results.add(interval);
        }

        return results;
    }
}

好像有点繁琐了，先存入treemap排序，key是start，value是end.

然后把这个treemap里的数据导入二维list。假设两个相邻的区间表示为e1=(x1,y1),e2=(x2,y2),一共有以下几种情况：

1. x2>y1: 将e1加入results集合；
2. x2<=y1: 将e1修改为(x1,Max(y1,y2)),并删除e2。

注意，在for循环的时候，每次循环最后本来都是i++的，但是如果执行的是以上步骤2，则i应该是不变的，因为链表里已经删除了一个元素了！所以需要执行一次i--;