2406. 将区间分为最少组数(中等)

Posted on In Views:

1，问题描述

2406. 将区间分为最少组数

难度：中等

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

示例 1：

1
2
3
4
5
6
7
输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
输出：3
解释：我们可以将区间划分为如下的区间组：
- 第 1 组：[1, 5] ，[6, 8] 。
- 第 2 组：[2, 3] ，[5, 10] 。
- 第 3 组：[1, 10] 。
可以证明无法将区间划分为少于 3 个组。

示例 2：

1
2
3
输入：intervals = [[1,3],[5,6],[8,10],[11,13]]
输出：1
解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。

提示：

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 106

2，初步思考

​ 堆处理

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package questions;

import java.util.*;

public class _2406将区间分为最少组数 {

    public int minGroups_gov(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            int temp = a[0] - b[0];
            return temp != 0 ? temp : -a[1] + b[1];
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>();// 最小堆
        for (int[] interval : intervals) {
            if (!pq.isEmpty() && pq.peek() < interval[0]) pq.poll();// 弹出最小值
            pq.add(interval[1]);// 更新数据
        }
        return pq.size();
    }

  	// 还是超时
    public int minGroups_optimize(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(interval);
        }
        Collections.sort(list, (a, b) -> {
            int temp = a[0] - b[0];
            return temp != 0 ? temp : -a[1] + b[1];
        });

        int res = 0;
        List<Integer> listIdx;
        while (!list.isEmpty()) {
            int right = 0;
            listIdx = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                int[] poll = list.get(i);
                if (right <= poll[0]) {
                    listIdx.addFirst(i);
                    right = poll[1];
                }
            }
            for (Integer idx : listIdx) {
                List<int[]> listTemp = list.subList(0, idx);
                listTemp.addAll(list.subList(idx + 1, list.size()));
                list = listTemp;
            }
            res++;
        }
        return res;
    }

    // 解法：优先队列处理，运行超时
    public int minGroups(int[][] intervals) {
        PriorityQueue<int[]> pq1 = new PriorityQueue<>((a, b) -> {
            int temp = a[0] - b[0];
            return temp != 0 ? temp : -a[1] + b[1];
        });
        PriorityQueue<int[]> pq2 = new PriorityQueue<>((a, b) -> {
            int temp = a[0] - b[0];
            return temp != 0 ? temp : -a[1] + b[1];
        });
        for (int[] interval : intervals) {
            pq1.offer(interval);
        }

        // 处理数据
        int res = 0;
        boolean isOne = true;
        while (!pq1.isEmpty() || !pq2.isEmpty()) {
            int right = 0;
            if (isOne) {
                while (!pq1.isEmpty()) {
                    int[] poll = pq1.poll();
                    if (right > poll[0]) {
                        pq2.add(poll);
                    } else {
                        right = poll[1];
                    }
                }
                res++;
                isOne = false;
            } else {
                while (!pq2.isEmpty()) {
                    int[] poll = pq2.poll();
                    if (right > poll[0]) {
                        pq1.add(poll);
                    } else {
                        right = poll[1];
                    }
                }
                res++;
                isOne = true;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        _2406将区间分为最少组数 minGroups = new _2406将区间分为最少组数();
        System.out.println(minGroups.minGroups_optimize(new int[][]{
//                {1, 2}, {2, 3}, {3, 4}, {2, 3}
//                {5,10},{6,8},{1,5},{2,3},{1,10}
                {441459, 446342}, {801308, 840640}, {871890, 963447}, {228525, 336985}, {807945, 946787}, {479815, 507766}, {693292, 944029}, {751962, 821744}
        }));
    }
}