56. Merge Intervals - Medium

前往題目

之前寫的文章

想法

• 先sort再用掃描線加入
• 這次只差條件沒寫好

思路

1. 先照start point由小到大排序，才能讓可以merge的排在一起
2. 接著疊代所有區間，遇到起始點小於等於暫存區間的終點等於有重疊，先merge但還不要加入答案，因為有可能好幾個區間都重疊

Code

class Solution {
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> res = new ArrayList<>();

        // Sort by start point
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);

        int[] temp = intervals[0];
        for (int i = 0; i < intervals.length; ++i) {
            // Merge
            if (intervals[i][0] <= temp[1]) {
                // Decide the end point
                temp[1] = Math.max(intervals[i][1], temp[1]);
            } else {
                res.add(temp);
                // Update temp interval
                temp = intervals[i];
            }
        }

        // Add the last interval
        res.add(temp);

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