MergeIntervals.java

class Solution {
    public int[][] merge(int[][] intervals) {
        Map<Integer, Integer> intervalMap = new HashMap<>();
        for (int[] interval: intervals) {
            intervalMap.putIfAbsent(interval[0], 0);
            intervalMap.compute(interval[0], (k, v) -> v > interval[1] ? v : interval[1]);
        }
        Map<Integer, Integer> merged = new HashMap<>();
        List<Integer[]> out = new LinkedList<>();
        int minStart = -1, maxEnd = -1;
        boolean isNewInterval = true;
        for (int k = 0 ; k <= 10000; k++) {
            if (intervalMap.containsKey(k)) {
                if (isNewInterval) {
                    minStart = k;
                    isNewInterval = false;
                }
                
                maxEnd = Math.max(maxEnd, intervalMap.get(k));
            }
            if (k == maxEnd) {
                out.add(new Integer[]{minStart, maxEnd});
                isNewInterval = true;
                continue;
            }
            
        }
        
        if (out.isEmpty()) {
            out.add(new Integer[]{minStart, maxEnd});
        } else {
            Integer[] last = out.get(out.size() - 1);
            if (last[1] != maxEnd) {
                out.add(new Integer[]{minStart, maxEnd});
            }
        }
        
        int[][] outArr = new int[out.size()][2];
        int i = 0;
        for (Integer[] mergedInt: out) {
            outArr[i++] = new int[]{mergedInt[0], mergedInt[1]};
        }
        
        return outArr;
    }
}