问题陈述:
我有一个WareHouses的列表。WareHouse有两个属性,即openingTimeclosingTime

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());
    }

10-07 19:48
查看更多