PriorityQueue

PriorityQueue好题选编

Greedy必备，甚至能代替DP！

2830. Maximize the Profit as the Salesman

反思：

• 并非所有求最大值的pq都是根据值倒序，不要死脑筋
• 可以利用pq的顺序上的有序性，另外用max来记录最值

public int maximizeTheProfit(int n, List<List<Integer>> offers) {
    Collections.sort(offers,(a,b)->(a.get(0)-b.get(0)));
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[0]-b[0]));
    //end,sum
    //once can append, all following ones can also append
    int max=0; //max value that can be appended
    for (List<Integer> offer : offers) {
        int start=offer.get(0);
        int end=offer.get(1);
        int val=offer.get(2);
        //each interval in pq only need to be considered once
        while(!pq.isEmpty() && pq.peek()[0]<start){
            max=Math.max(max,pq.poll()[1]);
        }
        pq.offer(new int[]{end,max+val});
    }
    while(!pq.isEmpty()){
        max=Math.max(max,pq.poll()[1]);
    }
    return max;
}

1235. Maximum Profit in Job Scheduling

注意：

• max有两用：代表当前job之前可以append的最大profit ,也最终代表最大profit

public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    convert(startTime,endTime,profit);
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[0]-b[0]));
    //end,sum
    int n=startTime.length;
    int max=0;
    for (int i = 0; i < n; i++) {
        int start=startTime[i];
        int end=endTime[i];
        int p=profit[i];
        //only pop when can be appended
        //once can be appended, all following job also can append it 
        while(!pq.isEmpty() && pq.peek()[0]<=start){
            max=Math.max(max,pq.poll()[1]);
        }
        pq.offer(new int[]{end,p+max});
    }
    while(!pq.isEmpty()){
        max=Math.max(max,pq.poll()[1]);
    }
    return max;
}

private void convert(int[] startTime, int[] endTime, int[] profit){
    List<int[]> list=new ArrayList<>();
    int n=startTime.length;
    for (int i = 0; i < n; i++) {
        list.add(new int[]{startTime[i],endTime[i],profit[i]});
    }
    Collections.sort(list,(a,b)->(a[0]-b[0]));
    for (int i = 0; i < n; i++) {
        int[] arr=list.get(i);
        startTime[i]=arr[0];
        endTime[i]=arr[1];
        profit[i]=arr[2];
    }
}