现有n件任务和⽆限多台的机器,任务可以在机器上得到处理。每件任务的开始时间为s i,完成时间为fi, si < fi 。[si, fi]为处理任务i的时间范围。两个任务i,j重叠是指两个任务的时间范围区间有重叠,⽽并⾮是指i,j的起点或终点重合。每台机器在任何时刻最多只处理⼀个任务。最优分配是指使⽤的机器最少的可⾏分配⽅案.用java实现
时间: 2024-03-23 14:39:57 浏览: 13
可以使用和上面Python代码类似的思路来实现Java代码。
首先,定义一个任务类,包括开始时间和结束时间:
```java
class Task {
int start;
int end;
public Task(int start, int end) {
this.start = start;
this.end = end;
}
}
```
然后,按照结束时间从小到大排序任务列表,并使用哈希表来记录每台机器的结束时间:
```java
public static int minMachines(Task[] tasks) {
Arrays.sort(tasks, (t1, t2) -> t1.end - t2.end);
Map<Integer, Integer> machines = new HashMap<>();
for (Task task : tasks) {
boolean assigned = false;
for (Map.Entry<Integer, Integer> entry : machines.entrySet()) {
if (task.start >= entry.getValue()) {
entry.setValue(task.end);
assigned = true;
break;
}
}
if (!assigned) {
machines.put(machines.size(), task.end);
}
}
return machines.size();
}
```
其中,`tasks`是任务列表,`machines`是哈希表,键为机器的编号,值为机器的结束时间。在遍历任务列表时,依次将任务分配到最早结束的可用机器上,如果没有可用机器,则需要再添加一台新的机器。
使用示例:
```java
Task[] tasks = {new Task(0, 3), new Task(1, 4), new Task(3, 6), new Task(5, 7), new Task(5, 9), new Task(6, 8), new Task(8, 10)};
int minMachines = minMachines(tasks);
System.out.println(minMachines); // 输出 3
```