网易2019实习生招聘编程第3题——牛牛找工作

为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。

输出描述:
对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。

输入例子1:

3 3 
1 100 
10 1000 
1000000000 1001 
9 10 1000000000

输出例子1:

100 
1000 
1001

---

基本思想就是：排序+二分查找

public  static void  f3() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();//n工作数 ， m小伙伴数量  
        List<Entry> data = new ArrayList<>();
        //读取数据
        for (int i = 0; i < n; i++) {
            int h = scan.nextInt(), p = scan.nextInt();
            data.add(new Entry(h, p));  
        }

        //自定义比较器 Comparator
        Comparator<Entry> cmp = new Comparator<Entry>() {
            @Override
            public int compare(Entry o1, Entry o2) {
                // TODO Auto-generated method stub
                return o1.hard - o2.hard;
            }
        };

        //排序数据
        Collections.sort(data, cmp);

        //更新maxHashMap <i, value> 表示0~i之间最大的薪酬value.
        Map<Integer, Integer> maxHashMap = new HashMap<>();
        for (int i = 0, max = Integer.MIN_VALUE; i < data.size(); i++) {
            Entry e = data.get(i);
            int p = e.money;
            if (max < p) {
                maxHashMap.put(i, p);
                max = p;
            } else {
                maxHashMap.put(i, max);
            }   
        }

        //debug
        System.out.println("===");
        System.out.println(maxHashMap);
        System.out.println(data);

        //为每个小伙伴寻找最高的薪酬
        for (int i = 0; i < m; i++) {
            int ability = scan.nextInt();
            Entry e = new Entry(ability, -1);
            int index = Collections.binarySearch(data, e, cmp);
            if (index < 0) {//没找到 但是包含该entry的插入位置
                index =  Math.abs(index + 1) - 1;//index的取值范围为-1~m-1                   
            } else {//找到对应的entry，但是需要找到最右边的entry对应的下标，以保证能得到最大的薪酬值。
                int hard = data.get(index).hard;                
                while (index < data.size() && data.get(index).hard == hard) index++;
                index = index - 1;          
            }
            System.out.println(index == -1 ? 0 : maxHashMap.get(index));    
        }       
    }

    /**
     * 自定义 工作难度--薪酬 类
     */
    static class Entry {
        int hard,  money;       
        public Entry(int hard, int money) {
            super();
            this.hard = hard;
            this.money = money;
        }

        @Override
        public String toString() {
            // TODO Auto-generated method stub
            return "[" + hard + "," + money + "]";
        }       
    }