Course Schedule III
Mahabharata — Dronacharya's Curriculum — Take as Many Courses as Possible Before Deadlines
समय सीमा से पहले — अधिकतम पाठ्यक्रम। सबसे लम्बा निकालो — यदि समय सीमा उल्लंघन हो॥
*Before deadline — maximum courses. Remove the longest — if deadline violated.*
The Story
Each course has a duration `duration[i]` and a deadline `lastDay[i]` (must finish by this day). Find the maximum number of courses that can be taken.
For `courses=[[100,200],[200,1300],[1000,1250],[2000,3200]]`: answer=3.
**Sort by deadline + Max-heap of durations:** - Sort courses by deadline (greedy: attend earlier-deadline courses first) - Use max-heap to track durations of selected courses - For each course: if current time + duration ≤ deadline → take it (add to heap, update time) - If not: if this course is shorter than the longest we've taken, swap them (remove longest, take this shorter one)
```java Arrays.sort(courses, (a,b)->a[1]-b[1]); // Sort by deadline PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a); // Max-heap of durations int time=0; for (int[] c : courses) { if (time + c[0] <= c[1]) { // Can take this course time += c[0]; pq.offer(c[0]); } else if (!pq.isEmpty() && pq.peek() > c[0]) { // Can improve by swapping time -= pq.poll(); time += c[0]; pq.offer(c[0]); } // else: skip (can't fit and no improvement possible) } return pq.size(); ```
Trace `[[100,200],[200,1300],[1000,1250],[2000,3200]]`: - Sort by deadline: [[100,200],[1000,1250],[200,1300],[2000,3200]] - [100,200]: 0+100≤200 → take. time=100. pq=[100] - [1000,1250]: 100+1000=1100≤1250 → take. time=1100. pq=[1000,100] - [200,1300]: 1100+200=1300≤1300 → take. time=1300. pq=[1000,200,100] - [2000,3200]: 1300+2000=3300>3200. pq.peek()=1000>2000? No (1000<2000). Skip. - return pq.size()=3 ✓
The Exhaustive Subset Checker
Try all 2^n subsets; for each, check if schedule is feasible (sorted by deadline, cumulative time ≤ deadline). Return max size feasible subset. O(2^n × n log n).
// Exponential — not practical
// Key insight: sort by deadline, use greedyDronacharya's Sort-Swap Greedy Wisdom
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (a, b) -> a[1] - b[1]); // Sort by deadline
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int time = 0;
for (int[] c : courses) {
if (time + c[0] <= c[1]) {
time += c[0];
pq.offer(c[0]);
} else if (!pq.isEmpty() && pq.peek() > c[0]) {
time -= pq.poll();
time += c[0];
pq.offer(c[0]);
}
}
return pq.size();
}Step-by-Step Walkthrough
[[3,2],[4,3]] Sort: [[3,2],[4,3]] (deadlines 2,3) [3,2]: 0+3=3>2. pq empty → skip. [4,3]: 0+4=4>3. pq empty → skip. Return 0 ✅ (neither course fits)
Deep Insight
**The swap insight:** Swapping a shorter course for the longest previously taken course: - Doesn't change the count (still same number of courses) - Reduces total time (by diff = prev_max - current_dur) - Makes it easier to fit FUTURE courses
This is an exchange argument: the swap is always beneficial when possible (current duration < max in heap).
**Sort by deadline:** Process earlier deadlines first. A course with an earlier deadline is harder to fit later, so handle it first (similar to scheduling by earliest deadline first in job scheduling theory).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(2^n × n) | O(n) | Exponential |
| Optimal | O(n log n) | O(n) | Sort O(n log n) + each course one heap op O(log n) |
Pattern Recognition
✅ Sort by deadline + max-heap of durations ✅ If fits: add to heap, update time ✅ If doesn't fit but shorter than max: swap ✅ Return heap.size() = number of courses taken **LeetCode Trigger Phrases:** → "course schedule III" maximum courses → Deadline-sorted greedy with duration heap → Exchange-swap optimization pattern
Bhagavad Gita 3.35
श्रेयान्स्वधर्मो विगुणः परधर्मात्स्वनुष्ठितात्। स्वधर्मे निधनं श्रेयः परधर्मो भयावहः॥
Better is one's own dharma, though imperfectly performed, than the dharma of another well performed. Better is death in one's own dharma; the dharma of another brings fear.
Connection: The course scheduler chooses the best possible curriculum within given constraints — not greedily taking all courses but wisely selecting those that fit the available time before each deadline. Like the Gita's teaching to do one's own duty within one's capacity rather than overreaching, the algorithm swaps a long course for a shorter one when necessary — a humble admission that sometimes less is more, and doing what fits one's current capacity is better than failing to complete something too ambitious.