大疆笔试 8.14
题目：假设我们有一批任务需要调度执行， 每个任务j(j=0,1...n-1)拥有一个权重wj，我们的目标是调度权重累加和最大
的的任务子集执行。已知任务到达的时刻为sj，终止的时刻为fj (注意，这里fj为任务结束的时刻，而不是执行时长)。
只有当两个任务的执行时间区间没有重叠的情况下， 这两个任务才能被调度先后执行，否则只能选其中之一调度执行。
编写一个函数schedule，输入一个包含n个任务信息的数组 (列表) [wj sj fj], j=0,1...n-1(0,1...n-1为任务
索引)，例如，在下面示例中，任务0的信息为[3 0 6]， 其中3为该任务的权重，0为任务到达时刻， 6为任务终
止时刻。返回可调度的最优任务子集(即： 该任务子集权重和最大)所对应的任务索引 (输出的任务索引按升序
排列)。为简化输出结果测试，假设最优解只有一组 (测试用例中不会出现多组最优解的情况)。
注：如果任务1为[10 2 5],任务2为[9 5 7], 则任务1和任务2的执行时间区间没有重叠； 如果任务1为[10 2 5],
#大疆笔试##大疆#
的的任务子集执行。已知任务到达的时刻为sj，终止的时刻为fj (注意，这里fj为任务结束的时刻，而不是执行时长)。
只有当两个任务的执行时间区间没有重叠的情况下， 这两个任务才能被调度先后执行，否则只能选其中之一调度执行。
编写一个函数schedule，输入一个包含n个任务信息的数组 (列表) [wj sj fj], j=0,1...n-1(0,1...n-1为任务
索引)，例如，在下面示例中，任务0的信息为[3 0 6]， 其中3为该任务的权重，0为任务到达时刻， 6为任务终
止时刻。返回可调度的最优任务子集(即： 该任务子集权重和最大)所对应的任务索引 (输出的任务索引按升序
排列)。为简化输出结果测试，假设最优解只有一组 (测试用例中不会出现多组最优解的情况)。
注：如果任务1为[10 2 5],任务2为[9 5 7], 则任务1和任务2的执行时间区间没有重叠； 如果任务1为[10 2 5],
务2为[9 4 7], 则任务1和任务2的执行时间区间有重叠。
思路：时间来不及，就用暴力解了
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 输入：
* 8个任务，每个任务3个参数
* 然后8行
* 8 3
* 3 0 6
* 1 1 4
* 4 3 5
* 17 3 8
* 9 4 7
* 10 5 9
* 8 6 10
* 1 8 11
*
* 输出：
* 3 7
*/
public class Main {
static int maxVal;
static List<Integer> ans;
public static void dfs(int[][] map, int index, boolean[] visited, int val, List<Integer> path){
if(index == map.length){
if(val>maxVal){
maxVal = val;
ans = new ArrayList<>(path);
}
return;
}
int v = map[index][0];
boolean flag = true;
//先检查时间是否重叠,两端不用检查
for (int i = map[index][1]+1; i < map[index][2]; i++) {
if(visited[i]){
flag = false;
break;
}
}
if(flag){
//选当前任务
for (int i = map[index][1]; i <= map[index][2]; i++) {
visited[i] = true;
}
path.add(index);
dfs(map, index+1, visited, val+v, path);
for (int i = map[index][1]; i <= map[index][2]; i++) {
visited[i] = false;
}
path.remove(path.size()-1);
}
//不选当前任务
dfs(map, index+1, visited, val, path);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int[][] map = new int[n][3];
for (int i = 0; i < n; i++) {
int val = sc.nextInt();
int start = sc.nextInt();
int end = sc.nextInt();
map[i][0] = val;
map[i][1] = start;
map[i][2] = end;
min = Math.min(min, start);
max = Math.max(max, end);
}
maxVal = 0;
ans = new ArrayList<>();
boolean[] visited = new boolean[max+1];
dfs(map, 0, visited, 0, new ArrayList<>());
for (Integer an : ans) {
System.out.print(an + " ");
}
}
} 
投递牛客等公司
查看9道真题和解析