Greedy & intervals

Make the locally best choice and never look back: when that works, how to convince yourself it works, and the interval problems where it shines.

When greedy works, and when it does not#

Give change for 6 using coins [1, 3, 4]:

Strategy	Choice	Coins
greedy: largest coin first	4, 1, 1	3
optimal (DP)	3, 3	2

Taking 4 looked best but blocked the better answer. With Indonesian or US coin systems greedy happens to be optimal, but not for arbitrary coins. So for every greedy idea, ask: can taking the "best" option now ever hurt later?

Proving it: the exchange argument

Take any optimal solution. Show that swapping its first choice for the greedy choice keeps it valid and no worse. Repeat for each step. Then the greedy solution is optimal too. You do not need formal proofs in interviews, but trying to make this argument is how you catch wrong greedy ideas before coding them.

Interval scheduling: keep the most meetings#

Given meetings with start and end times, keep as many as possible with no overlap.

Greedy: sort by end time; take each meeting that starts after the last kept one ends.

Why end time: the meeting that finishes first leaves the most room for everything else. If an optimal schedule began with a different meeting, swapping in the earliest-ending one cannot create a conflict (it ends even earlier), so the schedule stays valid with the same count.

Trace [[1,3], [2,4], [3,5], [6,7]] (already sorted by end):

interval	starts after last end?	kept	last end
[1,3]	yes	1	3
[2,4]	2 < 3: no	1	3
[3,5]	3 ≥ 3: yes	2	5
[6,7]	yes	3	7

Three meetings kept; "minimum to remove" is 4 - 3 = 1.

Sorting by start instead would fail on [[1,10], [2,3], [4,5]]: it would keep [1,10] and nothing else.

Run the trace

The same greedy runs twice: sorted by end (correct), then sorted by start, on the counterexample:

schedule_trace.go

package main
 
import (
	"cmp"
	"fmt"
	"slices"
)
 
func keep(meetings [][2]int, by string) int {
	ms := slices.Clone(meetings)
	key := 1 // sort by end
	if by == "start" {
		key = 0
	}
	slices.SortFunc(ms, func(a, b [2]int) int { return cmp.Compare(a[key], b[key]) })
	kept, lastEnd := 0, -1
	for _, m := range ms {
		if m[0] >= lastEnd {
			kept++
			lastEnd = m[1]
			fmt.Printf("  %v keep (last end now %d)\n", m, lastEnd)
		} else {
			fmt.Printf("  %v overlaps, skip\n", m)
		}
	}
	return kept
}
 
func main() {
	fmt.Println("by end:")
	fmt.Println("  kept", keep([][2]int{{1, 3}, {2, 4}, {3, 5}, {6, 7}}, "end"))
 
	trap := [][2]int{{1, 10}, {2, 3}, {4, 5}}
	fmt.Println("by end, counterexample:")
	fmt.Println("  kept", keep(trap, "end"))
	fmt.Println("by start, counterexample:")
	fmt.Println("  kept", keep(trap, "start"))
}

Output

by end:
  [1 3] keep (last end now 3)
  [2 4] overlaps, skip
  [3 5] keep (last end now 5)
  [6 7] keep (last end now 7)
  kept 3
by end, counterexample:
  [2 3] keep (last end now 3)
  [4 5] keep (last end now 5)
  [1 10] overlaps, skip
  kept 2
by start, counterexample:
  [1 10] keep (last end now 10)
  [2 3] overlaps, skip
  [4 5] overlaps, skip
  kept 1

Merging overlapping intervals#

Sort by start. Walk through; if the next interval starts at or before the end of the last merged one, extend that one's end; otherwise start a new merged interval.

Trace [[1,3], [2,6], [8,10], [9,12], [15,18]]:

interval	overlaps last?	merged list
[1,3]	first	[1,3]
[2,6]	2 ≤ 3: yes, end = max(3,6)	[1,6]
[8,10]	8 > 6: no	[1,6] [8,10]
[9,12]	9 ≤ 10: yes	[1,6] [8,12]
[15,18]	no	[1,6] [8,12] [15,18]

Run the trace

merge_trace.go

package main
 
import (
	"cmp"
	"fmt"
	"slices"
)
 
func main() {
	in := [][2]int{{8, 10}, {1, 3}, {15, 18}, {2, 6}, {9, 12}}
	slices.SortFunc(in, func(a, b [2]int) int { return cmp.Compare(a[0], b[0]) })
	fmt.Println("sorted by start:", in)
 
	var out [][2]int
	for _, iv := range in {
		if n := len(out); n > 0 && iv[0] <= out[n-1][1] {
			out[n-1][1] = max(out[n-1][1], iv[1])
			fmt.Printf("%v overlaps, extend -> %v\n", iv, out)
		} else {
			out = append(out, iv)
			fmt.Printf("%v new interval -> %v\n", iv, out)
		}
	}
}

Output

sorted by start: [[1 3] [2 6] [8 10] [9 12] [15 18]]
[1 3] new interval -> [[1 3]]
[2 6] overlaps, extend -> [[1 6]]
[8 10] new interval -> [[1 6] [8 10]]
[9 12] overlaps, extend -> [[1 6] [8 12]]
[15 18] new interval -> [[1 6] [8 12] [15 18]]

The input started unsorted on purpose: sorting by start is what guarantees overlapping intervals end up next to each other.

Jump Game#

Each nums[i] is the maximum jump length from index i. Can you reach the end? Track the farthest index reachable so far. If the loop ever reaches an index beyond it, you are stuck. Greedy works because reaching farther never hurts: every index before the frontier is reachable.

Run the trace

jump_trace.go

package main
 
import "fmt"
 
func canJump(nums []int) bool {
	far := 0 // farthest index reachable so far
	for i, n := range nums {
		if i > far {
			fmt.Printf("  i=%d is beyond the frontier %d: stuck\n", i, far)
			return false
		}
		far = max(far, i+n)
		fmt.Printf("  i=%d jump=%d frontier=%d\n", i, n, far)
	}
	return true
}
 
func main() {
	for _, nums := range [][]int{{2, 3, 1, 1, 4}, {3, 2, 1, 0, 4}} {
		fmt.Println(nums)
		fmt.Println("  reachable:", canJump(nums))
	}
}

Output

[2 3 1 1 4]
  i=0 jump=2 frontier=2
  i=1 jump=3 frontier=4
  i=2 jump=1 frontier=4
  i=3 jump=1 frontier=4
  i=4 jump=4 frontier=8
  reachable: true
[3 2 1 0 4]
  i=0 jump=3 frontier=3
  i=1 jump=2 frontier=3
  i=2 jump=1 frontier=3
  i=3 jump=0 frontier=3
  i=4 is beyond the frontier 3: stuck
  reachable: false

In the second case every path lands on the 0 at index 3, so the frontier stops growing at 3.

The full program#

greedy.go

package main
 
import (
	"cmp"
	"fmt"
	"slices"
)
 
func merge(intervals [][]int) [][]int {
	intervals = slices.Clone(intervals)
	slices.SortFunc(intervals, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })
	out := [][]int{slices.Clone(intervals[0])}
	for _, iv := range intervals[1:] {
		last := out[len(out)-1] // shares memory with out's element
		if iv[0] <= last[1] {
			last[1] = max(last[1], iv[1]) // edits the interval inside out
		} else {
			out = append(out, slices.Clone(iv))
		}
	}
	return out
}
 
func eraseOverlapIntervals(intervals [][]int) int {
	intervals = slices.Clone(intervals)
	slices.SortFunc(intervals, func(a, b []int) int { return cmp.Compare(a[1], b[1]) })
	kept, lastEnd := 0, 0
	for i, iv := range intervals {
		if i == 0 || iv[0] >= lastEnd {
			kept++
			lastEnd = iv[1]
		}
	}
	return len(intervals) - kept
}
 
func canJump(nums []int) bool {
	reach := 0
	for i, n := range nums {
		if i > reach {
			return false
		}
		reach = max(reach, i+n)
	}
	return true
}
 
func canCompleteCircuit(gas, cost []int) int {
	total, tank, start := 0, 0, 0
	for i := range gas {
		diff := gas[i] - cost[i]
		total += diff
		tank += diff
		if tank < 0 { // cannot reach i+1 from start: no station up to i works
			start, tank = i+1, 0
		}
	}
	if total < 0 {
		return -1
	}
	return start
}
 
func greedyCoins(coins []int, amount int) int {
	coins = slices.Clone(coins)
	slices.Sort(coins)
	count := 0
	for i := len(coins) - 1; i >= 0; i-- {
		count += amount / coins[i]
		amount %= coins[i]
	}
	return count
}
 
func main() {
	fmt.Println(merge([][]int{{8, 10}, {1, 3}, {2, 6}, {15, 18}, {9, 12}}))
	fmt.Println(eraseOverlapIntervals([][]int{{1, 3}, {2, 4}, {3, 5}, {6, 7}}))
	fmt.Println(canJump([]int{2, 3, 1, 1, 4}), canJump([]int{3, 2, 1, 0, 4}))
	fmt.Println(canCompleteCircuit([]int{1, 2, 3, 4, 5}, []int{3, 4, 5, 1, 2}))
	fmt.Println("greedy coins for 6 with [1 3 4]:", greedyCoins([]int{1, 3, 4}, 6))
	fmt.Println("greedy coins for 6 with [1 2 5]:", greedyCoins([]int{1, 2, 5}, 6))
}

Output

[[1 6] [8 12] [15 18]]
1
true false
3
greedy coins for 6 with [1 3 4]: 3
greedy coins for 6 with [1 2 5]: 2

Complexity#

Problem	Time	Space
merge intervals	O(n log n) (sorting)	O(n)
non-overlapping intervals	O(n log n)	O(1) besides the sort
jump game	O(n)	O(1)
gas station	O(n)	O(1)

Recognizing the pattern#

Intervals, meetings, schedules, "minimum number of rooms / arrows / removals": sort, then sweep.
"Can you reach…", "minimum number of jumps": track a frontier.
A choice that obviously dominates the others (smallest cookie that fits, earliest deadline).
If you can build a counterexample to the greedy choice in a minute, switch to DP.

Try it: minimum meeting rooms

The tip above, as code. Starts and ends are sorted separately; a start before the earliest unfinished end means another room is needed, otherwise a room is freed and reused:

rooms.go

package main
 
import (
	"fmt"
	"slices"
)
 
func minRooms(meetings [][2]int) int {
	var starts, ends []int
	for _, m := range meetings {
		starts = append(starts, m[0])
		ends = append(ends, m[1])
	}
	slices.Sort(starts)
	slices.Sort(ends)
	rooms, best, e := 0, 0, 0
	for _, s := range starts {
		if s < ends[e] {
			rooms++ // everyone is still busy
		} else {
			e++ // the earliest meeting has ended; reuse its room
		}
		best = max(best, rooms)
		fmt.Printf("start %2d, earliest end %2d: rooms in use %d\n", s, ends[e], rooms)
	}
	return best
}
 
func main() {
	fmt.Println("rooms needed:", minRooms([][2]int{{0, 30}, {5, 10}, {15, 20}, {10, 15}}))
}

Output

start  0, earliest end 10: rooms in use 1
start  5, earliest end 10: rooms in use 2
start 10, earliest end 15: rooms in use 2
start 15, earliest end 20: rooms in use 2
rooms needed: 2

Summary#

Greedy takes the locally best option and never revisits it; fast but not always correct.
Test greedy ideas with counterexamples and the exchange argument.
Max non-overlapping intervals: sort by end. Merging: sort by start.
Jump-style problems track the farthest reachable point.
When greedy fails, dynamic programming usually works.

Greedy & intervals

When greedy works, and when it does not#

Proving it: the exchange argument

Interval scheduling: keep the most meetings#

Run the trace

Merging overlapping intervals#

Run the trace

Jump Game#

Run the trace

The full program#

Complexity#

Recognizing the pattern#

Try it: minimum meeting rooms

Summary#

Check your understanding

Practice in Go