56. Merge Intervals

Merge Intervals - LeetCodeLeetCode

O(nlogn), O(n)

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0) return intervals;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        List<int[]> result = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        
        for (int interval[] : intervals) {
        // 這裡會是第一個元素先近來, 也沒差(預設s e 第一個元素
        // 跑完還是會第一個元素的 s e
            if (end >= interval[0]) { 
                end = Math.max(end, interval[1]); // for this case [[1,4],[2,3]]
            } else {
                result.add(new int[]{start, end});
                start = interval[0];
                end = interval[1];
            }
        }
        // 最後還要加上最後的 s e
        result.add(new int[]{start, end});
        
        return result.toArray(new int[result.size()][]);
    }
}

本題主要核心當然是

s1 e1

s2 e2

if s >= e 時 do merge(update end)

但是是用 start end 來表示

else

add data(to List), update start, end

注意 array sort

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

注意最後還要加

最後還要加上最後的 s e

和 list 如何轉 array

        return result.toArray(new int[result.size()][]);

newest version

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
            } else {
                res.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        res.add(new int[]{start, end});
        int[][] result = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}

/*
[[1,3],[2,6],[8,10],[15,18]]
  s       e
              s  e
                     s  e
1    3
   2    6
           8 10
                15 18
                
[[1,4],[2,3]]     so if (end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);   


1.    4
  2. 3
                
*/