// Runtime: 6 ms your runtime beats 88.61 % of java
class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> q = new LinkedList<>(Arrays.asList(intervals));

        ArrayList<int[]> r = new ArrayList<>();

        while (!q.isEmpty()){
            int[] i = q.remove();

            boolean merged;
            do{
               merged = false;
               Iterator<int[]> it = q.iterator();
                while (it.hasNext()) {
                int[] j = it.next();
                if (j[0] <= i[1] && j[1] >= i[0]) {
                    if (j[0] < i[0]) i[0] = j[0];
                    if (j[1] > i[1]) i[1] = j[1];
                    it.remove();
                    merged = true;
                }
              }
            } while (merged);
            r.add(i);
        }

        return r.toArray(new int [r.size()][2]);
    }
}


// Runtime: 6 ms your runtime beats 88.61 % of java submissions.
class Solution {
    public int[][] merge(int[][] intervals) {
       Arrays.sort(intervals,
                   new  Comparator<int[]>() {
                      public int compare (int[] a,int[] b) {
                          return a[0] > b[0] ? +1: a[0] < b[0] ? -1: a[1] - b[1];
                      }});

        ArrayList<int[]> r = new ArrayList<>();

        int[] last = null;
        for (int[] i: intervals) {
            if (last == null){
                last = i;
            } else if (i[0] > last[1]){
                r.add(last);
                last = i;
            } else if (i[1] > last[1]){
                last[1] = i[1];
            }
        }
        if (last != null) r.add(last);

        return r.toArray(new int [r.size()][2]);
    }
}