DPWORLD Coding Question – Solved

Question

You are given an integer 'n', indicating that there are n family members labeled from 1 to n. This large family completes dinner in several rounds due to limited seating at the dining table (k seats) and prerequisite relationships between members, which may be children eating first, senior members eating first, or any other reason. You are also given an array of relations where relations[i] = [member1, member2], representing prerequisite relationships where member1 must have dinner before member2.

Return the minimum number of rounds needed to have dinner for all members.

Note: The value of k is equal to the smallest prime factor of n.

Input Format:
- The first line of input contains an integer n.
- The second line contains an integer x (number of relations).
- The third line contains an integer 2 (indicates two integers are required in each relation).
- The next x lines each contain two integers representing a relation.

Constraints:
- 2 <= n <= 15
- 0 <= relations.length <= n * (n - 1) / 2
- relations[i].length == 2
- 1 <= member1, member2 <= n
- member1 != member2
- All the pairs [member1, member2] are unique.
- The given graph is a directed acyclic graph (DAG).

Output Format:
- Return an integer count that indicates the minimum number of rounds needed for all family members to take dinner.

Sample Testcase

Input:
4  
3
2  
2 1
3 1
1 4  

Output:
2

TreasuresBase Expert · Accepted Answer

from collections import defaultdict, deque
import heapq
def minNumberOfRounds(n,relations):
    indegree = defaultdict(int)
    h= defaultdict(set)
    for k in range(2,50):
        if n%k == 0:
            break
    for i, j in relations:
        indegree[j] +=1
        h[i].add(j)
    q = []
    visited = set()
    for i in range(1,n+1):
        if indegree[i] == 0:
            heapq.heappush(q,(-len(h[i]),i))
            visited.add(i)
    temp_time = 0
    while q:
        ln = len(q)
        for _in range(min(ln, k)):
            ignore1, node = heapq.heappop(q)
            for x in h[node]:
                indegree[x] -= 1
                if indegree[x] == 0:
                    visited.add(x)
                    heapq.heappush(q,(-len(h[x]),x))
        temp_time += 1
    return temp_time
import sys
n= int(input())
rl= int(input())

input()
if rl == 0:
    for k in range(2, 35):
        if n%k == 0:
            print(n//k)
            break
else:
    relations =[list(map(int,line.strip().split())) for line in sys.stdin]
    print(minNumberOfRounds(n,relations))

DPWORLD Coding Question – Solved

Image of the Question

All Testcases Passed ✔

Solution

🔒 Please login to view the solution

Explanation

Related Questions