华为题：在规定时间内完成任务的分配使得收益最大

image.png
很巧妙的贪心，直接看代码以及debug就可以

  1. public class Main {
  2.     public static void main(String[] args) {
  3.         int[] sla = new int[]{1, 1, 3, 3, 2, 2, 6};
  4.         int[] val = new int[]{6, 7, 2, 1, 4, 5, 1};
  6.         ArrayList<int[]> ints = new ArrayList<>();
  7.         for (int i = 0; i < val.length; i++) {
  8.             ints.add(new int[]{i, sla[i], val[i]});
  9.         }
  10.         Main main = new Main();
  11.         main.greedy(ints);
  12.     }
  13.     // datas: [id, deadlines, values]
  14.     public void greedy(ArrayList<int[]> datas) {
  15.         int len = datas.size();
  16.         System.out.println(len);
  17.         // 降序排列
  18.         datas.sort(((o1, o2) -> o2[2] - o1[2]));
  19.         datas.forEach(o -> {
  20.             System.out.println(Arrays.toString(o));
  21.         });
  22.         // 求和
  23.         int sum = datas.stream().mapToInt(data -> data[2]).sum();
  24.         System.out.println(sum);
  25.         // 占位，代表的是0-6这七个时间点，每一个时间点只能有一个任务
  26.         // 每个时间点只能有一个任务，因为每个任务需要一个小时完成
  27.         int[] routs = new int[len];
  29.         Arrays.fill(routs, -1);
  30.         int punish = 0;
  31.         // 对于每一个任务，三维的数据
  32.         for (int[] data : datas) {
  33.             // 从该任务的截止日期前一小时开始遍历空位，因为需要一小时进行解决
  34.             for (int j = data[1] - 1; j >= 0; j--) {
  35.                 // 如果存在空位的话，占最前面的一个位置，将id放入占位
  36.                 if (routs[j] == -1) {
  37.                     routs[j] = data[0];
  38.                     break;
  39.                 }
  40.                 // 如果遍历到最后都没有空位了，就说明这个选不到，记为不需要的，最后减
  41.                 // 不需要与空位中的数据进行比较的原因是，进行了降序排列
  42.                 if (j == 0)
  43.                     punish += data[2];
  44.             }
  45.         }
  46.         System.out.println(sum - punish);
  47.     }
  48. }