2022.01.04 - SX09-20.合并区间

2022.01.04 - SX09-20.合并区间

文章目录

• 1. 题目
• 2. 思路
• • (1) 贪心算法
• 3. 代码

1. 题目

2. 思路 (1) 贪心算法

• 若当前区间的左端小于等于前一区间的右端，则合并区间，否则，将前一区间加入结果集。

3. 代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        List res = new ArrayList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] <= right) {
                right = Math.max(right, intervals[i][1]);
            } else {
                res.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        res.add(new int[]{left, right});
        return res.toArray(new int[0][]);
    }
}