Graphs and dynamic programming · Lesson 23 of 23
Greedy: the best choice right now
When the locally best choice leads to the global best, and how to be sure.
Greedy picks what looks best at each step and never revisits it. When it works it's the fastest, simplest solution (often O(n), or O(n log n) with sorting). The catch: it's not always right, so you need a justification.
// Interval scheduling: the most meetings in one room.
// Greedy rule: always take the meeting that ENDS first.
function maxMeetings(meetings) {
const sorted = [...meetings].sort((a, b) => a[1] - b[1])
let count = 0, freeAt = -Infinity
for (const [start, end] of sorted) {
if (start >= freeAt) { count++; freeAt = end }
}
return count
}
console.log(maxMeetings([[1, 4], [2, 3], [3, 5], [7, 9], [5, 8]]))
// Jump game: can you reach the end? Track the farthest reachable index.
function canJump(nums) {
let reach = 0
for (let i = 0; i < nums.length; i++) {
if (i > reach) return false
reach = Math.max(reach, i + nums[i])
}
return true
}
console.log(canJump([2, 3, 1, 1, 4]), canJump([3, 2, 1, 0, 4]))| Meeting | Ends | Taken? |
|---|---|---|
[2, 3] | 3 | Yes (ends first) |
[1, 4] | 4 | No, starts before 3 |
[3, 5] | 5 | Yes |
[5, 8] | 8 | Yes |
[7, 9] | 9 | No, starts before 8 |
Three meetings. Taking the earliest finisher leaves the most free time for the rest.
How do you know greedy is right?
The exchange argument: suppose a better solution doesn't start with your choice. Swap its first choice for yours; if it stays valid and no worse, your choice is safe. With meetings: any better schedule can swap its first meeting for the earliest finisher, which ends no later, so it can't clash with the rest.
Conversely, try small examples. A single counterexample is enough to move on to DP.
Quick question
Coins [1, 3, 4], amount 6. How many coins does greedy (take the largest that fits) use?
Exercise
Write bestProfit(prices): the most profit from buying and selling any number of times (holding at most one share at a time). It must print 7 0.
Expected output: 7 0
function bestProfit(prices) {
}
console.log(bestProfit([7, 1, 5, 3, 6, 4]), bestProfit([7, 6, 4, 3, 1]))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.