题解 | 餐馆

二分，寻找每一次能匹配上的比较大的桌子，实际上这道题还能用最大堆做。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//n张桌子
        int m = sc.nextInt();//m批客人
        int[] table = new int[n];
        int[][] customers = new int[m][2];

        for (int i = 0; i < n; i++) {
            table[i] = sc.nextInt();
        }

        for (int i = 0; i < m; i++) {
            customers[i][0] = sc.nextInt();
            customers[i][1] = sc.nextInt();
        }
        
        Arrays.sort(customers, (a, b) -> b[1] - a[1]);
        Arrays.sort(table);

        long ans = 0L;
        int[] used = new int[n];

        for (int i = 0; i < m; i++) {
            if (table[n - 1] <
                    customers[i][0]) { 
                continue;
            }
            int num = customers[i][0];
            int price = customers[i][1];

            //找到合适的桌子坐
            int idx = binarySearch(num, table);
            while (idx < n && used[idx] == 1) {
                idx++;
            }
            if (idx < n) {
                ans += price;
                used[idx] = 1;
            }
        }
        System.out.println(ans);
    }

    //二分查找
    public static int binarySearch(int target, int[] table) {
        int l = -1;
        int r = table.length;
        while (l + 1 < r) {
            int mid = (l + r) >>> 1;
            if (table[mid] >= target) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
}