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 II

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 an array relations where relations[i] = [prevCourse_i, nextCourse_i], representing a prerequisite relationship between course prevCourse_i and course nextCourse_i: course prevCourse_i has to be taken before course nextCourse_i. Also, you are given the integer k. In one semester, you can take at most k courses as long as you have taken all the prerequisites in the previous semesters for the courses you are taking. Return the minimum number of semesters needed to take all courses. The test cases will be generated such that it is possible to take every course.

Key Insights

  • The problem can be modeled as a directed acyclic graph (DAG) where nodes represent courses and edges represent prerequisites.
  • A topological sort can help determine the order of course completion based on prerequisites.
  • A bitmask can be used to represent the state of completed courses, allowing for dynamic programming.
  • We need to explore different combinations of courses that can be taken in each semester while respecting the limit k.

Space and Time Complexity

Time Complexity: O(n * 2^n)
Space Complexity: O(2^n)

Solution

The solution uses a dynamic programming approach combined with bit manipulation. We maintain a DP array where dp[mask] represents the minimum number of semesters needed to complete the courses represented by the bitmask mask.

  1. Graph Representation: Build an adjacency list and an array to keep track of in-degrees for each course.
  2. Bitmask DP: Iterate through all possible states (bitmasks) representing completed courses. For each state, determine which courses can be taken in the current semester by checking their prerequisites.
  3. Course Selection: For each valid subset of courses that can be taken (up to k), update the DP array for the new state formed by adding these courses.
  4. Final Result: The minimum number of semesters to complete all courses will be in dp[(1 << n) - 1], where all courses are completed.

Code Solutions

from collections import defaultdict, deque

def minNumberOfSemesters(n, relations, k):
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)

    # Build graph and in-degree array
    for u, v in relations:
        graph[u].append(v)
        in_degree[v] += 1

    # Initialize DP array
    dp = [float('inf')] * (1 << n)
    dp[0] = 0  # Starting with no courses taken

    # Iterate over all masks
    for mask in range(1 << n):
        # Count how many courses can be taken in this semester
        available_courses = []
        for course in range(1, n + 1):
            if (mask & (1 << (course - 1))) == 0:  # Course not taken yet
                if in_degree[course] == 0:  # No prerequisites
                    available_courses.append(course)

        # Generate combinations of courses to take
        m = len(available_courses)
        for i in range(1 << m):
            if bin(i).count('1') > k:  # Exceeding the limit
                continue

            new_mask = mask
            for j in range(m):
                if (i & (1 << j)) > 0:
                    new_mask |= (1 << (available_courses[j] - 1))
            
            # Update DP for new mask
            dp[new_mask] = min(dp[new_mask], dp[mask] + 1)

        # Update in-degrees for the next iteration
        for course in available_courses:
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1

    return dp[(1 << n) - 1]
← Back to All Questions