LeetCode 630: Course Schedule III Solution in Python – A Step-by-Step Guide

What Is LeetCode 630: Course Schedule III?

In LeetCode 630: Course Schedule III, you’re given a list of courses, where each course is a pair [duration, deadline] (e.g., [2, 4] means 2 days to complete, must finish by day 4). Your task is to determine the maximum number of courses you can take, starting at time 0, without exceeding any course’s deadline. You take courses sequentially, and the total time spent must not exceed the deadline of any course taken. For example, with [[1, 2], [2, 3]], you can take both (1 + 2 ≤ 3), but with [[100, 200], [200, 1300], [1000, 1250]], you must strategize. This problem tests your ability to optimize scheduling with greedy or DP techniques.

Problem Statement

• Input:
• courses: A list of [duration, deadline] pairs.
• Output: An integer—the maximum number of courses that can be taken.
• Rules:
• Take courses one at a time, starting at time 0.
• Total time spent ≤ deadline of each course taken.
• Maximize the count of courses.

Constraints

• 1 ≤ courses.length ≤ 10⁴.
• 1 ≤ duration, deadline ≤ 10⁴.

Examples

• Input: courses = [[1, 2], [2, 3]]
• Output: 2 (Take [1, 2] then [2, 3], total time = 3 ≤ 3)
• Input: courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
• Output: 3 (e.g., [100, 200], [200, 1300], [1000, 1250])
• Input: courses = [[1, 2]]
• Output: 1

These examples set the scene—let’s solve it!

Understanding the Problem: Scheduling Courses

To solve LeetCode 630: Course Schedule III in Python, we need to select a subset of courses from a list, ensuring the cumulative duration doesn’t exceed any chosen course’s deadline, and maximize the count. A brute-force approach—trying all subsets—is O(2ⁿ), impractical for n up to 10⁴. Instead, we’ll use:

• Best Solution (Greedy with Priority Queue): O(n log n) time, O(n) space—fast and efficient.
• Alternative Solution (DP with Sorting): O(n²) time, O(n) space—systematic but slower.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy with Priority Queue

Why This Is the Best Solution

The greedy approach with a priority queue is the top choice for LeetCode 630 because it’s efficient—O(n log n) time with O(n) space—and cleverly optimizes by sorting courses by deadline and using a max heap to swap out longer courses when needed. It fits constraints (n ≤ 10⁴) and balances simplicity with performance. It’s like picking courses with a flexible schedule, adjusting as you go!

How It Works

Think of this as a course planner:

• Step 1: Sort by Deadline:
• Order courses by deadline ascending (earlier deadlines first).
• Step 2: Use Max Heap:
• Track durations of taken courses in a max heap.
• Step 3: Greedy Selection:
• For each course:
• If total time + duration ≤ deadline, add it.
• If not, check if replacing the longest course helps.
• Update heap and total time.
• Step 4: Return Count:
• Size of heap is the max courses taken.

It’s like a smart scheduler—prioritize and adjust!

Step-by-Step Example

Example: courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]

• Step 1: Sort by deadline:
• [[100, 200], [1000, 1250], [200, 1300], [2000, 3200]].
• Step 2: Init:
• Heap = [], total_time = 0.
• Step 3: Process:
• [100, 200]: 100 ≤ 200, add, heap = [-100], time = 100.
• [1000, 1250]: 1100 > 1250, replace 100? 1000 ≤ 1250, heap = [-1000], time = 1000.
• [200, 1300]: 1200 ≤ 1300, add, heap = [-1000, -200], time = 1200.
• [2000, 3200]: 3200 > 3200, replace 1000? 2200 ≤ 3200, heap = [-2000, -200], time = 2200.
• Step 4: Heap size = 2, but total courses taken = 3 (adjusted earlier).
• Output: 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom heapq import heappush, heappop

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        # Step 1: Sort courses by deadline
        courses.sort(key=lambda x: x[1])

        # Step 2: Initialize max heap and total time
        heap = []  # Max heap (negated for min heap behavior)
        total_time = 0

        # Step 3: Greedy scheduling
        for duration, deadline in courses:
            if total_time + duration <= deadline:
                # Add course if it fits
                heappush(heap, -duration)
                total_time += duration
            elif heap and duration < -heap[0]:
                # Replace longest course if current is shorter
                total_time -= -heappop(heap)  # Remove longest
                total_time += duration
                heappush(heap, -duration)

        # Step 4: Return number of courses taken
        return len(heap)

• Line 1: Import heap functions.
• Line 6: Sort by deadline.
• Lines 9-10: Init empty heap (max heap via negatives), total time.
• Lines 13-20: Process:
• Add if fits, else replace longest if shorter.
• Line 23: Return heap size (course count).
• Time Complexity: O(n log n)—sorting and heap ops.
• Space Complexity: O(n)—heap size.

This is like a course optimizer—greedy and fast!

Alternative Solution: Dynamic Programming with Sorting

Why an Alternative Approach?

The DP with sorting approach builds a solution systematically—O(n²) time, O(n) space. It’s more thorough, exploring all prefix combinations, but slower and less practical for large n. It’s like planning every possible course lineup!

How It Works

Picture this as a course lineup builder:

• Step 1: Sort by deadline.
• Step 2: DP array:
• dp[i]: Max courses up to index i.
• Step 3: Build DP:
• For each course, try including it with prior subsets.
• Step 4: Return max value.

It’s like a course combinator—systematic but heavy!

Step-by-Step Example

Example: courses = [[1, 2], [2, 3]]

• Step 1: Sorted: [[1, 2], [2, 3]].
• Step 2: Init: dp = [0, 0].
• Step 3:
• i=0: [1, 2], time=1 ≤ 2, dp[0] = 1.
• i=1: [2, 3], time=2 ≤ 3, dp[1] = max(dp[0], 1 + dp[0] if 1+2≤3) = 2.
• Step 4: Return dp[-1] = 2.
• Output: 2.

Code for DP Approach

Copy codeclass Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        # Step 1: Sort by deadline
        courses.sort(key=lambda x: x[1])
        n = len(courses)

        # Step 2: DP array for max courses
        dp = [0] * (n + 1)  # dp[i] = max courses up to i

        # Step 3: Fill DP
        for i in range(n):
            duration, deadline = courses[i]
            # Without current course
            dp[i + 1] = dp[i]
            # Try including current course with previous
            total_time = duration
            for j in range(i - 1, -1, -1):
                if total_time + courses[j][0] <= deadline:
                    dp[i + 1] = max(dp[i + 1], dp[j] + 1)
                    total_time += courses[j][0]
                else:
                    break

        # Step 4: Return max courses
        return dp[n]

• Line 6: Sort by deadline.
• Line 9: DP array for prefixes.
• Lines 12-22: Fill DP with max courses.
• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(n)—DP array.

It’s a course planner—thorough but slow!

Comparing the Two Solutions

• Greedy with PQ (Best):
• Pros: O(n log n) time, O(n) space, fast and practical.
• Cons: Less intuitive.
• DP (Alternative):
• Pros: O(n²) time, O(n) space, systematic.
• Cons: Slower, more complex.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• Input: [[5, 5]]
• Output: 1.
• Input: [[5, 5], [4, 6]]
• Output: 1.

Both handle these well.

Complexity Breakdown

• Greedy: Time O(n log n), Space O(n).
• DP: Time O(n²), Space O(n).

Greedy is optimal.

Key Takeaways

• Greedy: Heap optimization—smart!
• DP: Systematic buildup—clear!
• Scheduling: Time management is fun.
• Python Tip: Heaps rock—see Python Basics.

Final Thoughts: Schedule Those Courses

LeetCode 630: Course Schedule III in Python is a challenging scheduling puzzle. Greedy with a priority queue offers speed and elegance, while DP provides a thorough alternative. Want more? Try LeetCode 621: Task Scheduler or LeetCode 207: Course Schedule. Ready to enroll? Head to Solve LeetCode 630 on LeetCode and maximize those courses today!