Loading repovive.com/roadmaps/greedy-algorithms
Roadmaps
Greedy Algorithms
Array Greedy Problems
Problemset
Discussion
AI Helper
Introduction to Greedy
0/36
1
Intro
2
The Core Idea
3
Vocabulary - Greedy Choice
4
Vocabulary - Optimal Substructure
5
Quiz: Two Properties
6
When Greedy Works
7
When Greedy Fails
8
Greedy vs Brute Force
9
Greedy vs Dynamic Programming
10
Quiz: Greedy vs DP
11
The Greedy Template
12
Example - Coin Change (Greedy Works)
13
Why Greedy Works for US Coins
14
Example - Coin Change (Greedy Fails)
15
Lesson from Coin Change
16
Quiz: Coin Change
17
Problem - Assign Cookies
18
Assign Cookies - The Idea
19
Assign Cookies - Algorithm
20
Assign Cookies - Walkthrough
21
Assign Cookies - Implementation
22
Assign Cookies - Why Greedy Works
23
Lessons from Assign Cookies
24
Problem - Lemonade Change
25
Lemonade - The Idea
26
Lemonade - Algorithm
27
Lemonade - Implementation
28
Quiz: Lemonade Greedy Choice
29
Lessons from Lemonade
30
The Sorting Question
31
Common Greedy Patterns
32
The Greedy Mindset
33
Quiz: Greedy Mindset
34
Time Complexity of Greedy
35
What is Next
36
Section Recap
Proving Greedy Correctness
0/42
1
Intro
2
The Problem with Intuition
3
Two Proof Techniques
4
Vocabulary - Exchange Argument
5
Exchange Argument Structure
6
Quiz: Exchange Argument
7
Example - Activity Selection Exchange
8
Activity Selection - The Exchange
9
Activity Selection - Completing the Proof
10
When Exchange Works Best
11
Vocabulary - Stays Ahead Argument
12
Stays Ahead Structure
13
Quiz: Stays Ahead
14
Example - Activity Selection Stays Ahead
15
Activity Selection - Base Case
16
Activity Selection - Inductive Step
17
Activity Selection - Conclusion
18
When Stays Ahead Works Best
19
Exchange vs Stays Ahead
20
Quiz: Choosing a Technique
21
Finding Counterexamples
22
Counterexample - 0/1 Knapsack
23
Counterexample - Better Example
24
Counterexample - The Classic
25
Why Greedy Fails for 0/1 Knapsack
26
How to Find Counterexamples
27
Quiz: Counterexample Thinking
28
Problem - Minimum Waiting Time
29
Minimum Waiting - The Greedy Claim
30
Minimum Waiting - Exchange Proof
31
Minimum Waiting - Algorithm
32
Problem - Tandem Bicycle
33
Tandem Bicycle - Maximize Speed
34
Tandem Bicycle - Minimize Speed
35
Tandem Bicycle - Proof Sketch
36
Problem - Class Photos
37
Class Photos - Greedy Solution
38
Class Photos - Proof
39
Quiz: Class Photos
40
Common Proof Mistakes
41
Practice Strategy
42
Section Recap
Activity Selection
0/43
1
Intro
2
Problem - Activity Selection
3
Trying the Example
4
Wrong Approach 1 - Earliest Start
5
Wrong Approach 2 - Shortest Duration
6
Wrong Approach 3 - Fewest Conflicts
7
The Correct Approach
8
Quiz: Sort Order
9
The Algorithm
10
Walkthrough
11
Implementation
12
Proof Overview
13
Proof Step 1 - First Activity
14
Proof Step 2 - Induction
15
Proof Step 3 - Conclusion
16
Quiz: Exchange Argument
17
Lessons from Activity Selection
18
Problem - N Meetings in One Room
19
Problem - Non-overlapping Intervals
20
Non-overlapping - Walkthrough
21
Non-overlapping - Implementation
22
Quiz: Problem Transformation
23
Problem - Minimum Arrows
24
Minimum Arrows - The Idea
25
Minimum Arrows - Algorithm
26
Minimum Arrows - Walkthrough
27
Minimum Arrows - Implementation
28
Comparing the Three Problems
29
Handling Edge Cases
30
Quiz: Edge Cases
31
Variant - Weighted Activity Selection
32
Why Weighted Needs DP
33
Problem - Meeting Rooms I
34
Meeting Rooms I - Algorithm
35
Problem - Meeting Rooms II
36
Meeting Rooms II - Approach 1
37
Meeting Rooms II - Walkthrough
38
Meeting Rooms II - Approach 2
39
Meeting Rooms II - Implementation
40
Quiz: Meeting Rooms II
41
Activity Selection vs Meeting Rooms
42
What is Next
43
Section Recap
Interval Problems
0/44
1
Intro
2
The Interval Pattern
3
Problem - Merge Intervals
4
Merge Intervals - The Idea
5
Merge Intervals - Algorithm
6
Merge Intervals - Walkthrough
7
Merge Intervals - Implementation
8
Quiz: Merge Intervals
9
Problem - Insert Interval
10
Insert Interval - Algorithm
11
Insert Interval - Implementation
12
Lessons from Merge and Insert
13
Problem - Interval List Intersections
14
Interval Intersections - Algorithm
15
Interval Intersections - Implementation
16
Quiz: Interval Intersections
17
Problem - Remove Covered Intervals
18
Remove Covered - Algorithm
19
Remove Covered - Implementation
20
Problem - Minimum Intervals to Cover
21
Minimum Cover - Algorithm
22
Minimum Cover - Implementation
23
Quiz: Interval Covering
24
Why Sort by End Time?
25
Quiz: Sort Order Choice
26
Problem - Non-overlapping Intervals
27
Non-overlapping - The Idea
28
Non-overlapping - Implementation
29
Problem - Meeting Rooms
30
Meeting Rooms - Algorithm
31
Meeting Rooms - Implementation
32
Problem - Meeting Rooms II
33
Meeting Rooms II - Event Sweep
34
Meeting Rooms II - Implementation
35
Quiz: Meeting Rooms
36
The Sweep Line Pattern
37
Problem - My Calendar I
38
My Calendar I - Algorithm
39
My Calendar I - Implementation
40
Interval Overlap Check
41
Quiz: Interval Overlap
42
Comparing Interval Patterns
43
What is Next
44
Section Recap
Array Greedy Problems
0/41
1
Intro
2
Problem - Jump Game
3
Jump Game - The Idea
4
Jump Game - Walkthrough
5
Jump Game - Implementation
6
Quiz: Jump Game
7
Problem - Jump Game II
8
Jump Game II - Algorithm
9
Jump Game II - Implementation
10
Problem - Gas Station
11
Gas Station - The Idea
12
Gas Station - Implementation
13
Quiz: Gas Station
14
Problem - Boats to Save People
15
Boats - Algorithm
16
Boats - Implementation
17
Problem - Candy
18
Candy - Algorithm
19
Candy - Implementation
20
Quiz: Two-Pass Pattern
21
Problem - Maximum Subarray
22
Kadane's Algorithm
23
Kadane's - Implementation
24
Kadane's - Why It Works
25
Quiz: Kadane's Algorithm
26
Problem - Best Time to Buy and Sell Stock
27
Stock - The Idea
28
Stock - Implementation
29
Problem - Best Time to Buy and Sell Stock II
30
Stock II - Greedy Insight
31
Stock II - Implementation
32
Quiz: Stock Trading
33
Problem - Partition Labels
34
Partition Labels - Algorithm
35
Partition Labels - Implementation
36
Problem - Queue Reconstruction by Height
37
Queue Reconstruction - Greedy Insight
38
Queue Reconstruction - Implementation
39
Quiz: Greedy Ordering
40
What is Next
41
Section Recap
Greedy Optimization
0/38
1
Intro
2
Problem - Fractional Knapsack
3
Fractional Knapsack - Algorithm
4
Fractional Knapsack - Implementation
5
0/1 Knapsack - Why Greedy Fails
6
Quiz: Knapsack
7
Problem - Job Sequencing
8
Job Sequencing - Algorithm
9
Job Sequencing - Implementation
10
Problem - Minimum Platforms
11
Minimum Platforms - Implementation
12
Problem - Task Scheduler
13
Task Scheduler - Algorithm
14
Task Scheduler - Implementation
15
Quiz: Task Scheduler
16
Task Scheduler - Why This Works
17
Problem - Reorganize String
18
Reorganize String - Feasibility
19
Reorganize String - Algorithm
20
Reorganize String - Implementation
21
Quiz: Reorganize String
22
Problem - IPO
23
IPO - Greedy Insight
24
IPO - Implementation
25
Problem - Minimum Cost to Hire K Workers
26
Hire Workers - The Idea
27
Hire Workers - Implementation
28
Quiz: Worker Hiring
29
Problem - Couples Holding Hands
30
Couples - Greedy Approach
31
Couples - Implementation
32
The Greedy Optimization Pattern
33
Problem - Assign Cookies
34
Assign Cookies - Greedy Insight
35
Assign Cookies - Implementation
36
Quiz: Greedy Matching
37
What is Next
38
Section Recap
Advanced Greedy
0/37
1
Intro
2
Problem - Huffman Coding
3
Huffman - Algorithm
4
Huffman - Implementation
5
Problem - Reorganize String
6
Reorganize String - Algorithm
7
Reorganize String - Implementation
8
Quiz: Reorganize String
9
Problem - Remove K Digits
10
Remove K Digits - Algorithm
11
Remove K Digits - Implementation
12
Remove K Digits - Why Greedy
13
Quiz: Remove K Digits
14
Problem - Create Maximum Number
15
Create Maximum - Subproblems
16
Create Maximum - Max from One Array
17
Create Maximum - Merge Step
18
Create Maximum - Full Solution
19
Problem - Patching Array
20
Patching Array - The Idea
21
Patching Array - Implementation
22
Quiz: Patching Array
23
Problem - Candy Crush
24
Candy Crush - Algorithm
25
Candy Crush - Implementation
26
Problem - Minimum Number of Arrows
27
Arrows - Greedy Insight
28
Arrows - Implementation
29
Quiz: Arrows vs Activity Selection
30
Problem - Minimum Increment to Make Array Unique
31
Make Unique - Greedy Approach
32
Make Unique - Implementation
33
Advanced Greedy Patterns
34
When Greedy Gets Tricky
35
Quiz: Advanced Greedy
36
What is Next
37
Section Recap
Practice Problems
0/35
1
Intro
2
How to Practice Greedy
3
Problem - Maximize Sum of Array After K Negations
4
K Negations - Greedy Approach
5
K Negations - Implementation
6
Quiz: K Negations
7
Problem - Minimum Cost to Connect Sticks
8
Connect Sticks - Greedy Insight
9
Connect Sticks - Implementation
10
Problem - Two City Scheduling
11
Two City - Greedy Insight
12
Two City - Implementation
13
Problem - Bag of Tokens
14
Bag of Tokens - Two Pointer Greedy
15
Bag of Tokens - Implementation
16
Quiz: Bag of Tokens
17
Problem - Broken Calculator
18
Broken Calculator - Reverse Greedy
19
Broken Calculator - Implementation
20
Problem - Minimum Deletions to Make Character Frequencies Unique
21
Minimum Deletions - Greedy Approach
22
Minimum Deletions - Implementation
23
Problem - Valid Parenthesis String
24
Valid Parenthesis - Greedy Range
25
Valid Parenthesis - Implementation
26
Problem - Wiggle Subsequence
27
Wiggle Subsequence - Greedy Insight
28
Wiggle Subsequence - Implementation
29
Quiz: Wiggle Subsequence
30
Summary: Greedy Problem Categories
31
Easy Problems
32
Medium Problems
33
Hard Problems
34
What is Next
35
Section Recap