Activity Selection
The classic greedy problem. Select the maximum number of non-overlapping activities by deadline.
Lessons
1. Intro
The gateway problem
2. Problem - Activity Selection
The classic setup
3. Trying the Example
Finding the answer
4. Wrong Approach 1 - Earliest Start
Why it fails
5. Wrong Approach 2 - Shortest Duration
Why it fails
6. Wrong Approach 3 - Fewest Conflicts
Why it fails
7. The Correct Approach
Earliest end time
8. Quiz: Sort Order
Test your understanding
9. The Algorithm
Step by step
10. Walkthrough
Tracing the algorithm
11. Implementation
The code
12. Proof Overview
Why it is optimal
13. Proof Step 1 - First Activity
The greedy choice
14. Proof Step 2 - Induction
Extending the argument
15. Proof Step 3 - Conclusion
G is optimal
16. Quiz: Exchange Argument
Test your understanding
17. Lessons from Activity Selection
Key patterns
18. Problem - N Meetings in One Room
Same problem, different story
19. Problem - Non-overlapping Intervals
Minimum removals
20. Non-overlapping - Walkthrough
Tracing the algorithm
21. Non-overlapping - Implementation
The code
22. Quiz: Problem Transformation
Recognize equivalence
23. Problem - Minimum Arrows
Burst balloons
24. Minimum Arrows - The Idea
Grouping overlapping balloons
25. Minimum Arrows - Algorithm
Sort and shoot
26. Minimum Arrows - Walkthrough
Tracing the algorithm
27. Minimum Arrows - Implementation
The code
28. Comparing the Three Problems
Same pattern, different questions
29. Handling Edge Cases
Empty input and ties
30. Quiz: Edge Cases
Touching intervals
31. Variant - Weighted Activity Selection
When greedy fails
32. Why Weighted Needs DP
A counterexample
33. Problem - Meeting Rooms I
Can attend all?
34. Meeting Rooms I - Algorithm
Simple overlap check
35. Problem - Meeting Rooms II
Minimum rooms needed
36. Meeting Rooms II - Approach 1
Event-based counting
37. Meeting Rooms II - Walkthrough
Tracing the events
38. Meeting Rooms II - Approach 2
Min-heap method
39. Meeting Rooms II - Implementation
The code
40. Quiz: Meeting Rooms II
Apply the algorithm
41. Activity Selection vs Meeting Rooms
Different questions
42. What is Next
Looking ahead
43. Section Recap
What we learned