刷了一圈牛客神州信息的算法题竟然一样

第二题正确思路0(nlogm)的时间复杂度,n为capacity的大小,m为arr的大小

import java.util.*;

public class Main {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[] capacity = new int[n];
    int[][] arr = new int[m][2];
    for (int i = 0; i < n; i++) {
        capacity[i] = in.nextInt();
    }
    for (int i = 0; i < m; i++) {
        arr[i][0] = in.nextInt();
        arr[i][1] = in.nextInt();
    }
    Arrays.sort(capacity);
    Arrays.sort(arr, (a, b) -> {
        return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
    });
    long ans = 0;
    PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) ->{
        return b - a;
    });
    int l = 0;
    for(int i = 0;i < n;i++){
        int j = lower_bound(arr,capacity[i] + 1);
        for(int k = l;k < j;k++){
            queue.offer(arr[i][1]);
        }
        if(!queue.isEmpty()){
            ans += queue.poll();
        }
        l = j;
    }
    System.out.println(ans);
}
public static int lower_bound(int[][] arr,int t){
    int l = -1,r = arr.length;
    while(l + 1 < r){
        int m = (l + r) >> 1;
        if(arr[m][0] >= t){
            r = m;
        }else{
            l = m;
        }
    }
    return r;
}

}