We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Parallel Courses III

Difficulty: Hard

Problem Description

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCourse_j, nextCourse_j] denotes that course prevCourse_j has to be completed before course nextCourse_j (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.

You must find the minimum number of months needed to complete all the courses following these rules:

  • You may start taking a course at any time if the prerequisites are met.
  • Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Key Insights

  • The problem can be modeled as a directed acyclic graph (DAG) where courses are nodes and prerequisites are directed edges.
  • Each course has a specific time required to complete, and we need to account for the completion times of prerequisite courses.
  • A topological sort can be employed to determine the order of course completion while considering the time constraints.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of courses and m is the number of relations.
Space Complexity: O(n + m), for storing the graph and in-degree of each course.

Solution

To solve the problem, we will use a topological sorting approach with a queue. We will maintain an array to keep track of the time taken to complete each course, taking into account the time required for its prerequisites. We will:

  1. Build a graph representation of the courses and their prerequisites.
  2. Use an in-degree array to track the number of prerequisites for each course.
  3. Initialize a queue with courses that have no prerequisites (in-degree of 0).
  4. Process courses in the queue, updating the total time required for each course based on the completion times of its prerequisites.
  5. Continue until all courses are processed, keeping track of the maximum time taken for the last course.

Code Solutions

from collections import defaultdict, deque

def minimumTime(n, relations, time):
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)
    completion_time = [0] * (n + 1)
    
    # Build the graph and in-degree array
    for prev, next in relations:
        graph[prev].append(next)
        in_degree[next] += 1
    
    # Initialize queue with courses that have no prerequisites
    queue = deque()
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            queue.append(i)
            completion_time[i] = time[i - 1]
    
    # Process the queue
    while queue:
        course = queue.popleft()
        
        for next_course in graph[course]:
            in_degree[next_course] -= 1
            completion_time[next_course] = max(completion_time[next_course], completion_time[course] + time[next_course - 1])
            if in_degree[next_course] == 0:
                queue.append(next_course)
    
    return max(completion_time)
← Back to All Questions