工单调度策略

SLA【2021优招、2022校招题目】

【华为校园招聘软件】 2022-04-13

编程题 （第2/3题）

【编程题目 | 200分】工单调度策略 [ 2022 考试题 ]

2、工单调度策略

■ 题目描述

• 当小区通信设备上报警时，系统会自动生成待处理的工单，工单调度系统需要根据不同的策略，调度外线工程师（FME）上站去修复工单对应的问题。
• 根据与运营商签订的合同，不同严重程度的工单被处理并修复的时长要求不同，这个要求被修复的时长我们称之为SLA时间。
• 假设华为与运营商A签订了运维合同，部署了一套调度系统，只有1个外线工程师（FME），每个工单根据问题严重程度会给一个评分，在SLA时间内完成修复的工单，华为员工获得工单对应的积分，超过SLA完成的工单不获得积分，但必须完成该工单，运营商最终会根据积分付款。
• 请设计一种调度策略，根据现状得到调度结果完成所有工单，让这个外线工程师处理的工单处理的工单获得的总积分最多。
• 假设从某个调度时刻开始，当前工单数量N，不会产生新的工单，每个工单处理修复耗时为1小时。请设计你的调度策略，完成业务目标。
• 不考虑外线工程师在小区之间行驶的耗时。

输入

• 第一行为一个整数N，表示工单的数量。
• 接下来N行，每行包括两个整数，第一个整数表示工单的SLA时间（小时），第二个数表示工单的积分。

输出

• 输出一个整数表示可以获得的最大积分。

样例 1

假设有7个工单的SLA时间（小时）和积分如下：

最多可获得15积分，其中一个调度结果完成工单顺序为2，6，3，1，7，5，4（可能还有其他顺序）。

输入

7

1 6

1 7

3 2

3 1

2 4

2 5

6 1

输出

15

提示：

工单数量 N ≤ 106

SLA时间 ≤ 7 × 105

答案的最大积分不会超过2147483647

代码实现

CPP

剩余50%内容，订阅会员后查看

JAVA

剩余50%内容，订阅会员后查看

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class T2 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] nums = new int[n][2];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 2; j++) {
        nums[i][j] = sc.nextInt();
      }
    }
    Arrays.sort(nums,((a, b) -> {
      if (a[0] != b[0]) {
        return a[0] - b[0];
      } else {
        return b[1] - b[0];
      }
    }));
    PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));
    int cur = 0;
    for (int i = 0; i < n; i++) {
      int time = nums[i][0];
      int score = nums[i][1];
      if (time > cur) {
        cur++;
        queue.offer(nums[i]);
      } else if (!queue.isEmpty() && queue.peek()[1] < score) {
        queue.poll();
        queue.offer(nums[i]);
      }
    }
    int res = 0;
    while (!queue.isEmpty()) {
      res += queue.poll()[1];
    }
    System.out.println(res);
  }
}

STICK永久会员

打赏 收藏 海报 链接