[面試真題]-具有依賴關系的任務執行

題目

要求任務之間有一定的依賴關系，若b依賴于a，則a任務執行完成之後，b才能執行。所有任務都同時到達且串行執行，求任務的最小平均響應時間。

輸入執行個體：

5 6  # 5為任務個數 6為關系個數
1 2 1 1 1 # 分别為任務1到任務5的執行時間
1 2 # 任務2依賴于任務1，下同
1 3
1 4
2 5
3 5
4 5
           

輸出

1 3 4 2 5
           

算法

public class Main{
    static class Task{
        int id;
        int time;
        int waits = 0;
        LinkedList<Integer> refs = new LinkedList<>();
        public Task(int id, int time) {
            this.id = id;
            this.time = time;
        }

    }
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        PriorityQueue<Task> can = new PriorityQueue<>((o1, o2) -> {
            if (o1.waits<o2.waits)return -1;
            if(o1.waits>o2.waits)return 1;
            if(o1.time<o2.time)return -1;
            if(o1.time>o2.time)return 1;
            if(o1.id<o2.id)return -1;
            if(o1.id>o2.id)return 1;
            return 0;
        });
        int m,n;
        n = s.nextInt();
        m = s.nextInt();
        Task[] tasks = new Task[n+1];
        for (int i = 1; i <= n; i++) {
            int time = s.nextInt();
            tasks[i] = new Task(i,time);
        }
        for (int i = 0; i < m; i++) {
            int ai = s.nextInt();
            int bi = s.nextInt();
            tasks[bi].waits++;
            tasks[ai].refs.add(bi);
        }
        for (int i = 1; i <= n; i++) {

            if(tasks[i].waits==0)can.add(tasks[i]);
        }
        Task next = can.poll();
        StringBuilder builder = new StringBuilder();
        builder.append(next.id);
        while (next!=null){
            for (Integer t : next.refs) {
                Task temp = tasks[t];
                temp.waits--;
                if(temp.waits==0){
                    can.add(temp);
                }
            }
            next = can.poll();
            if(next!=null){
                builder.append(" "+next.id);

            }
        }
        System.out.println(builder.toString());

    }
}
           

思路：由于是串行執行任務，我們維護一個優先級隊列

1. 優先級隊列判定規則：先判斷執行時間長短，短的優先，再判斷id大小，小的優先
2. 每個節點維護一個等待節點個數·

   wait

   ，

   wait

   為0時才能放入優先級隊列中執行
3. 從優先級隊列中取任務執行每執行一個任務，則将其所有後繼任務數的

   wait

   進行

   wait--