/*
1. 在区间一侧, 如果起点相近的区间不能融合, 那么较远的必定也不能, 所以按起点排序
2. 排序后从左到右尝试合并区间, 
如果可以合并修改右侧区间继续尝试
否则加入结果集后继续尝试

3. 区间合并包含几种情况.  [a,b] [c,d]   -> acbd acdb  边界可以相等
*/

class Solution {

    class Node{
        int s,e;
        public Node(int s, int e){
            this.s = s;
            this.e = e;
        }
    }

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return intervals;

        List<Node> list = new ArrayList<>();
        List<Node> result = new ArrayList<>();

        for (int i = 0 ; i < intervals.length ; i++){
            int s = Math.min(intervals[i][0], intervals[i][1]);
            int e = Math.max(intervals[i][0], intervals[i][1]);
            list.add(new Node(s,e));
        }

        list.sort((a,b)->(a.s == b.s ? a.e-b.e : a.s-b.s));

        for (int i = 0 ; i < list.size()-1; i++){
            Node node = list.get(i);
            Node next = list.get(i+1);
            if (check(node, next)) {
                next.s = Math.min(node.s, next.s);
                next.e = Math.max(node.e, next.e);
            } else {
                result.add(node);
            }
        }
        result.add(list.get(list.size()-1));
        int[][] answer = new int[result.size()][2];
        for (int i = 0 ; i < result.size(); i ++){
            Node node = result.get(i);
            answer[i][0] = node.s;
            answer[i][1] = node.e;
        }

        return answer;
    }

    private boolean check(Node cur, Node next){
        if (cur.s <= next.s  && next.s <= cur.e && cur.s <= next.e) return true;
        return false;
    }
}