2.1 最好收入的工作

考点：贪心+有序表TreeMap（优化查询）

🐌1. 题目描述

:::info 给定数组hard和money，长度都为N，hard[i]表示i号工作的难度，money[i]表示i号工作的收入。
给定数组ability，长度都为M，ability[j]表示j号人的能力，每一号工作，都可以提供无数的岗位，难度和收入都一样。但是人的能力必须>=这份工作的难度，才能上班。
返回一个长度为M的数组ans，ans[j]表示j号人能获得的最好收入。 :::

💡2. 解决思路

贪心：难度相同的工作选择收入高的，收入相同时选择难度较低的工作
因此对数组处理之后剩余hard和money数组应该是工作难度和对应的收入应该是同步递增的关系。

🚩3. 代码实现

package class02;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;
public class Code01_ChooseWork {
    public static class Job {
        public int money;
        public int hard;
        public Job(int m, int h) {
            money = m;
            hard = h;
        }
    }
    // 定义排序规则：按照工作难度排序，难度相同的工作选择收入高的
    public static class JobComparator implements Comparator<Job> {
        @Override
        public int compare(Job o1, Job o2) {
            return o1.hard != o2.hard ? (o1.hard - o2.hard) : (o2.money - o1.money);
        }
    }
    public static int[] getMoneys(Job[] job, int[] ability) {
        // 对原始数组进行排序
        Arrays.sort(job, new JobComparator());
        // key : 难度   value：报酬
        TreeMap<Integer, Integer> map = new TreeMap<>();
        // 第一组数据
        map.put(job[0].hard, job[0].money);
        // pre : 上一份进入map的工作
        Job pre = job[0];
        // 对数组数据进行预处理，处理之后保证工作难度和对应的收入应该是同步递增的关系
        for (int i = 1; i < job.length; i++) {
            if (job[i].hard != pre.hard && job[i].money > pre.money) {
                pre = job[i];
                map.put(pre.hard, pre.money);
            }
        }
        int[] ans = new int[ability.length];
        for (int i = 0; i < ability.length; i++) {
            // ability[i] 当前人的能力 <= ability[i]  且离它最近的
            Integer key = map.floorKey(ability[i]);
            ans[i] = key != null ? map.get(key) : 0;
        }
        return ans;
    }
}