56. Merge Interval

T: O(nlogn)

S: O(n)

use start = -1 idea, timeline cant be -1, so it's safe.

class Solution {
    public int[][] merge(int[][] intervals) {
        
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] interval : intervals) {
            map.put(interval[0], map.getOrDefault(interval[0], 0) + 1);
            map.put(interval[1], map.getOrDefault(interval[1], 0) + -1);
        }
        
        List<int[]> res = new ArrayList<>();
        int start = -1;
        int count = 0;
        for (int key : map.keySet()) {
            if (start == -1) {
                start = key;
            }
            int value = map.get(key);
            count += value;
            if (count == 0) {
                res.add(new int[]{start, key});
                start = -1;
            }
        }
        int[][] result = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}
/*
if count == 0

1   -1
1.  3
  2.   6  
  1    -1       8. 10
*/

or just set start = key, when count == 0 (before add new time)

class Solution {
    public int[][] merge(int[][] intervals) {
        
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] interval : intervals) {
            map.put(interval[0], map.getOrDefault(interval[0], 0) + 1);
            map.put(interval[1], map.getOrDefault(interval[1], 0) + -1);
        }
        
        List<int[]> res = new ArrayList<>();
        int start = 0;
        int count = 0;
        for (int key : map.keySet()) {
            if (count == 0) {
                start = key;
            }
            int value = map.get(key);
            count += value;
            if (count == 0) {
                res.add(new int[]{start, key});
            }
        }
        int[][] result = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}