【排序 + 优先队列 】数对组数问题

题目描述：

给定二维数组 intervals，intervals[i] = {left , right} (符合数对定义)。请你将二维数组分组， 保证组内区间不重叠，函数返回最小分组数。

示例：

思路：

1. 排序 ：先对二维数组按第一列元素从大到小排序
2. 借助优先队列， 判断组数：
   a. 若 队列等于空 或者 当前遍历元素的 intervals[i][0] <= q.peek() ，则将 ans++，并将*intervals[i][1]*加入优先队列
   b. 若队列不等于空，且 intervals[i][0] > q.peek() ，则则优先队列最小元素出队列，并将 intervals[i][1] 加入优先队列

执行图解

代码：

 public int minGroups(int[][] intervals) {
        //思路 —— 优先队列 + 贪心
        int ans = 0;
        Arrays.sort(intervals, (a, b)-> a==b ? a[1] - b[1] : a[0]  - b[0]);
        Queue<Integer> q = new PriorityQueue<>();
        for(int i=0; i<intervals.length; i++){
            if(!q.isEmpty() && intervals[i][0] > q.peek()){
                q.poll();
            } else{
                ans++;
            }
            q.offer(intervals[i][1]);
        }
        return ans;
    }         
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为什么可以想到优先队列

其实不是优先队列的问题，而是对本题的关键在于，对每步的 intervals[i][0]，我们都需要将它与前面最小的 intervals[i][1] 比较，若是比较找到了最小的，自然不需要更新结果，只需将这个已经用过的 intervals[i][1] 移除即可。如果前面最小的 intervals[i][1] 都大于它了，就将结果加一。每步都找最小，记录的方法自然而然就可以想到优先队列。