问题陈述:
我有一个WareHouses
的列表。WareHouse
有两个属性,即openingTime
,closingTime
。
public class WareHouse {
private int startTime;
private int endTime;
}
有一组代理负责将产品交付到仓库,我需要计算能够将产品交付到所有仓库的所需代理的最小数量。
假设:当一个代理将产品运送到一个特定的仓库时,比如说W1{1,2},他只能在一个小时后(即仓库关闭时间)出来。
仓库{打开时间,关闭时间}
w1{1,2},w2{2,4},w3{3,6},w4{9,11},w5{10,11}
public static void main(String[] args) {
WareHouse w1 = new WareHouse(2, 4);
WareHouse w2 = new WareHouse(1, 2);
WareHouse w3 = new WareHouse(3, 6);
WareHouse w4 = new WareHouse(10, 11);
WareHouse w5 = new WareHouse(9, 11);
List<WareHouse> wareHouses = new ArrayList<WareHouse>();
wareHouses.add(w1);
wareHouses.add(w2);
wareHouses.add(w3);
wareHouses.add(w4);
wareHouses.add(w5);
}
理想情况下,它需要两个代理,那么如何为它设计算法呢?
我的方法:
将有一个后台作业来检查所有代理的状态。一旦一个代理接收到一个任务,我将把它的可用性设置为false一旦结束,我会把他重新加入代理队列然而,我在这里的主要挑战是如何猜测代理已经完成了任务,如何模拟此事件这将告诉我任务已经结束,已经2个小时了?
最佳答案
要计算最小代理数,不需要模拟交付过程。这是一个区间分割问题,你可以使用贪婪算法。查看https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms-2x2.pdf。
在您的例子中,您可以使用以下代理类(您需要仓库变量的getter,因为它们是私有的-我在这里没有显示):
public class Agent {
int lastFinishTime;
boolean isCompatibleWith(WareHouse x) {
return x.startTime > lastFinishTime;
}
boolean scheduleWareHouse(WareHouse x) {
lastFinishTime = x.endTime;
}
}
然后,您可以按如下方式应用间隔分区算法(同时使用代理的优先级队列,根据lastfishtime排序):
Sort warehouses by starting time so that s1 ≤ s2 ≤ ... ≤ sn.
d ← 0
for j = 1 to n {
if (warehouse j is compatible with some agent k)
schedule warehouse j to agent k
else
allocate a new agent d + 1
schedule warehouse j to agent d + 1
d ← d + 1
}
全面实施:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class Partition {
public static class WareHouse {
int startTime;
int endTime;
public WareHouse(int i, int j) {
startTime=i;
endTime=j;
}
}
public static class Agent {
int end;
public Agent() {
}
public boolean isCompWith(WareHouse x) {
return end <=x.startTime;
}
public void schedule(WareHouse x) {
end=x.endTime;
}
}
public static void main(String...args) {
WareHouse w1 = new WareHouse(2, 4);
WareHouse w2 = new WareHouse(1, 2);
WareHouse w3 = new WareHouse(3, 6);
WareHouse w4 = new WareHouse(10, 11);
WareHouse w5 = new WareHouse(9, 11);
List<WareHouse> wareHouses = new ArrayList<WareHouse>();
wareHouses.add(w1);
wareHouses.add(w2);
wareHouses.add(w3);
wareHouses.add(w4);
wareHouses.add(w5);
Collections.sort(wareHouses, new Comparator<WareHouse> (){
public int compare(WareHouse x, WareHouse y) {
return x.startTime - y.startTime;
}
});
PriorityQueue<Agent> queue =
new PriorityQueue<Agent>(new Comparator<Agent>() {
public int compare(Agent x, Agent y) {
return x.end- y.end;
}
});
for(WareHouse x: wareHouses) {
Agent a = queue.poll();
if(a==null) {
a=new Agent();
a.schedule(x);
queue.add(a);
}
else if (a.isCompWith(x)) {
a.schedule(x);
queue.add(a);
} else {
Agent b = new Agent();
b.schedule(x);
queue.add(a);
queue.add(b);
}
}
System.out.println(queue.size());
}