笔试题-Quality Management

目录

1. Input
2. Output
3. Constraints
4. Example

Answer

Description

In a manufacturing company Rexcord, N quality checks are needed to be accomplished todeliver a high quality product. Each quality check has a unique ID. Some of the qualitychecks need to be completed before the other quality check can be started. The quality

assurance manager wants to find the order in which the quality checks must be performedsuch that all the quality checks can be performed before delivering the product. If there ismore than one order possible then the quality check with smaller ID is performed first.

Write an algorithm to help the quality assurance manager find the order in which thequality checks must be performed such that all the quality checks can be performed.

Input

​ The input to the function/method consists of three arguments-

1. num, an integer representing the total number of quality checks to be performed.
2. dependecyCount, an integer representing the number of dependencies of quality checks.
3. dependencies, a list of integers where each element of the list consists of a pair of integers A and B representing the quality check IDs such that quality check A must be completed before the quality check B.

Output

​ Return the list of integers representing the quality checks in the order in which these must be performed such that all the quality checks can be performed. If no such order is possible then return the list with a single integer-1.

Constraints

​ 1 <= num < 1000

​ 0 <= dependecyCount <= num* num-1

0 <= dependencies[ij] < num

​ 0 <= i < dependecyCount

​ 0 <= j < 2

Example

​ Input:

​ num =6

​ dependecyCount =6

​ dependencies =[[2,3],[3,1],[4, 0],[4,1],[5, 0],[5, 2]]

​ Output:

​ [4,5,0,2,3,1]

​ Explanation:

​ The two possible orders in which the quality checks can be performed are: 4, 5, 0, 2,3,1 and 5,4,0,2,3,1

​ Now the final order in which the quality checks are performed will be the one in which the quality check with lower quality check ID is performed first. So, the output is [4,5,0,2, 3,1].

Answer

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.PriorityQueue;
public class Main {

    static class Solution
    {
        // METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
        List<Integer> qualityChecksOrder(int num, int dependecyCount,
                                         int[][] dependencies)
        {
            List <Integer> ans = new ArrayList<Integer>();
            List <Set<Integer>> fa = new ArrayList<Set<Integer>>();
            List <Set<Integer>> ch = new ArrayList<Set<Integer>>();
            for (int i = 0; i < num; i++) {
                fa.add(new HashSet<>());
                ch.add(new HashSet<>());
            }
            for (int i = 0; i < dependecyCount; i++) {
                fa.get(dependencies[i][1]).add(dependencies[i][0]);
                ch.get(dependencies[i][0]).add(dependencies[i][1]);
            }
            Queue<Integer> avl = new PriorityQueue<>();
            for (int i = 0; i < num; i++) {
                if (fa.get(i).isEmpty()) {
                    avl.add(i);
                }
            }
            if (avl.isEmpty()) {
                ans.add(-1);
            }
            else {
                while (!avl.isEmpty()) {
                    int cur = avl.poll();
                    for (int c: ch.get(cur)) {
                        fa.get(c).remove(cur);
                        if (fa.get(c).isEmpty()) {
                            avl.add(c);
                        }
                    }
                    ans.add(cur);
                }
            }
            if (ans.size() < num) {
                ans = new ArrayList<>();
                ans.add(-1);
            }
            return ans;
        }
        // METHOD SIGNATURE ENDS
    }

    public static void main(String[] args) {
        //Scanner sc = new Scanner(System.in);
        Solution s = new Solution();
        int [][] p = {{2,3}, {3,1}, {4,0}, {4,1}, {5,0}, {5,2}};
        for (int x :s.qualityChecksOrder(6, 6, p))
            System.out.println(x);
    }

}

这个题目与 leetcode 周赛 155 项目管理是类似的，就是少了一个分组，多了一个优先队列。

leetcode weekly 155 5200. 项目管理 1203. Sort Items by Groups Respecting Dependencies