贪心 + 优先队列：程序员PIPI-蒲公英云

贪心 + 优先队列：程序员PIPI

文章目录

贪心 + 优先队列：程序员PIPI
- - 问题：
  - 思路：
  - 代码：

问题：

在这里插入图片描述

思路：

本题实际上是要我们在坐标轴上找到区间重叠最多的那一段有多少个区间。
我们可以将进程按开始时间从小到大排序，我们的贪心策略是让一个计算机处理尽可能多的进程，为了达到这一目的，我们要让每个计算机的空闲时间尽可能少，即完成一个进程后尽快处理下一个进程，因此我们需要知道正在处理进程的所有计算机中，最早完成任务的计算机的完成时间，即正在被处理的进程的最早结束时间。若当前需要被处理的进程的开始时间大于等于正在被处理的进程的最早结束时间，则可以让这个最早完成任务的计算机来处理当前进程。
我们用一个优先队列来记录在所有处理进程的计算机中，最早处理完的时间（即进程的最早结束时间）。我们遍历进程，按以下情况进行不同处理：
1、当前优先队列为空，说明我们还没有使用任意一台计算机，我们开始使用第一台计算机处理当前进程，将当前进程的结束时间加入优先队列，机器数+1
2、当前进程的开始时间小于堆顶元素（即优先队列头）的结束时间，即当前区间与堆顶元素代表的区间有重叠，也就是需要使用一台新计算机来处理它，当前进程不能重用计算机，于是我们使用一台新计算机处理它，将当前进程的结束时间加入优先队列，机器数+1
3、当前进程的开始时间大于等于堆顶元素的结束时间，那么证明之后的所有区间（进程）都不会与堆顶元素所代表的区间重叠了，因此我们可以将堆顶元素弹出来，相当于将堆顶元素（进程）占用的计算机匀给了当前区间（进程），然后我们将当前区间（进程）的结束时间加入堆。
举个例子：
在这里插入图片描述

代码：

import java.util.*;
public class Main {
    static Pro[] array = new Pro[100002];
    static Queue<Integer> q = new PriorityQueue<>();
    public static void main(String[] args) {
        int n, s, t, i, ans;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            n = scanner.nextInt();
            ans = 0;
            q.clear();
            for (i = 0;i < n;i++) {
                s = scanner.nextInt();
                t = scanner.nextInt();
                array[i] = new Pro(s, t);
            }
            Arrays.sort(array, 0, n, new Comparator<Pro>() {
                @Override
                public int compare(Pro o1, Pro o2) {
                    return o1.s - o2.s;
                }
            });
            for (i = 0;i < n;i++) {
                if (q.isEmpty()) {
                    ans++;
                    q.add(array[i].t);
                } else if (array[i].s < q.peek()) {
                    ans++;
                    q.add(array[i].t);
                } else {
                    q.poll();
                    q.add(array[i].t);
                }
            }
            System.out.println(ans);
        }
    }
}
class Pro {
    public int s;
    public int t;
    public Pro (int s, int t) {
        this.s = s;
        this.t = t;
    }
}