14.11 Sorting Plus Greedy

Many greedy algorithms begin with a sort. The sort is not an implementation detail. It is often the step that exposes the structure needed for the greedy rule to work.

Without sorting, a greedy algorithm may see decisions in an arbitrary order and make choices before it has enough context. With sorting, the algorithm processes candidates according to the property that matters: finish time, deadline, profit, density, weight, start time, or some derived key. Once the right order is chosen, the remaining loop is often simple.

This recipe focuses on the design pattern:

Sort by the right key.
Scan once.
Make local decisions.

Problem

You have a collection of objects and need to choose, merge, discard, or arrange them optimally.

Examples:

Problem	Sort Key	Greedy Action
Interval scheduling	Finish time	Select compatible intervals
Fractional knapsack	Value density	Take highest-density items
Job sequencing	Profit	Schedule jobs late
Prefix constraints	Deadline	Remove longest job on violation
Merge intervals	Start time	Extend current interval
Minimum arrows for balloons	End coordinate	Shoot at earliest end

The hard part is not writing the loop. The hard part is choosing the sort key.

Why Sorting Matters

A greedy algorithm commits to decisions incrementally. Sorting gives those commitments a meaningful order.

For interval scheduling, sorting by finish time ensures that the first selected interval leaves the maximum space for the future.

For fractional knapsack, sorting by value density ensures that every unit of capacity is spent on the best available value rate.

For prefix constraints, sorting by deadline turns a global feasibility problem into a sequence of prefix checks.

In each case, sorting converts the problem into an ordered stream where local choices become valid.

The Basic Recipe

Use this template when a greedy problem appears to involve ordering.

Choose a candidate ordering.
Sort the input by that ordering.
Initialize an empty answer or state.
For each item in sorted order:
    If the item improves or preserves feasibility:
        accept it
    Otherwise:
        reject it or repair the state
Return the answer

The design question is:

What ordering makes a local choice safe?

Example 1: Merge Intervals

Given intervals:

[1,3], [2,6], [8,10], [15,18]

Merge overlapping intervals.

The correct sort key is start time.

Sorted input:

[1,3], [2,6], [8,10], [15,18]

Scan from left to right.

Maintain the current merged interval.

current = [1,3]

Next interval:

[2,6]

It overlaps because:

2 <= 3

Merge:

current = [1,6]

Next interval:

[8,10]

It does not overlap.

Emit:

[1,6]

Start new current interval:

[8,10]

Final result:

[1,6], [8,10], [15,18]

Sorting by start time guarantees that once an interval does not overlap the current merged interval, no later interval can begin earlier and repair that gap.

Go Implementation

type Interval struct {
	Start int
	End   int
}

func MergeIntervals(intervals []Interval) []Interval {
	if len(intervals) == 0 {
		return nil
	}

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i].Start < intervals[j].Start
	})

	result := make([]Interval, 0, len(intervals))
	current := intervals[0]

	for i := 1; i < len(intervals); i++ {
		next := intervals[i]

		if next.Start <= current.End {
			if next.End > current.End {
				current.End = next.End
			}
		} else {
			result = append(result, current)
			current = next
		}
	}

	result = append(result, current)
	return result
}

Example 2: Minimum Arrows to Burst Balloons

Each balloon is an interval on a line. One arrow shot at coordinate x bursts every balloon whose interval contains x.

Given:

[10,16], [2,8], [1,6], [7,12]

Goal:

Find the minimum number of arrows.

The right sort key is interval end.

Sorted by end:

[1,6], [2,8], [7,12], [10,16]

Shoot the first arrow at the earliest end:

x = 6

This bursts:

[1,6], [2,8]

Next unburst balloon:

[7,12]

Shoot:

x = 12

This bursts:

[7,12], [10,16]

Answer:

This is the same core idea as interval scheduling: choose the earliest possible endpoint that preserves maximum flexibility.

Go Implementation

func MinArrows(points []Interval) int {
	if len(points) == 0 {
		return 0
	}

	sort.Slice(points, func(i, j int) bool {
		return points[i].End < points[j].End
	})

	arrows := 1
	arrowPos := points[0].End

	for i := 1; i < len(points); i++ {
		if points[i].Start > arrowPos {
			arrows++
			arrowPos = points[i].End
		}
	}

	return arrows
}

Example 3: Non-Overlapping Intervals

Given a list of intervals, remove the minimum number of intervals so that the rest do not overlap.

This can be reframed as:

Keep the maximum number of non-overlapping intervals.

That is exactly interval scheduling.

Sort by end time.

Accept an interval if it starts after the last accepted end.

Count the rejected intervals.

func EraseOverlapIntervals(intervals []Interval) int {
	if len(intervals) == 0 {
		return 0
	}

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i].End < intervals[j].End
	})

	kept := 1
	lastEnd := intervals[0].End

	for i := 1; i < len(intervals); i++ {
		if intervals[i].Start >= lastEnd {
			kept++
			lastEnd = intervals[i].End
		}
	}

	return len(intervals) - kept
}

Choosing the Sort Key

A useful way to select a sort key is to ask what the algorithm is trying to preserve.

Goal	Usually Sort By	Reason
Leave maximum future time	Earliest finish	Frees future capacity
Spend capacity efficiently	Highest value density	Maximizes value per unit
Respect deadlines	Earliest deadline	Makes prefix checks meaningful
Prefer valuable jobs	Highest profit	Tries best opportunities first
Merge ranges	Earliest start	Reveals contiguous overlap
Minimize points covering intervals	Earliest end	Places point as early as safely possible

The sort key should align with the exchange argument. If no exchange argument appears, the sort key is probably only a heuristic.

Proof Pattern

Sorting plus greedy proofs usually have this shape.

First, show that the first item in sorted order is safe to process.

For interval scheduling, the earliest finishing interval can replace the first interval in some optimal schedule.

For fractional knapsack, the highest-density item can replace lower-density capacity usage.

For deadline scheduling, processing by deadline ensures that a violation at the current job captures the tightest relevant constraint.

Second, show that after accepting, rejecting, or repairing, the remaining problem has the same form.

This gives the algorithm its recursive justification, even if the implementation is iterative.

Common Mistakes

Sorting by the wrong key often produces plausible but incorrect algorithms.

For interval scheduling, sorting by start time fails.

For fractional knapsack, sorting by value fails.

For prefix constraints, processing without deadline order breaks the invariant.

For merging intervals, sorting by end time makes the scan harder and error-prone.

Another common mistake is using sorting as a substitute for proof. A sorted greedy algorithm can still be wrong. The sort key must be justified by a local-safety argument.

Complexity Analysis

Most sorting plus greedy algorithms run in:

O(n log n)

because sorting dominates.

The scan is usually:

O(n)

Space is often:

O(1)

excluding the output, unless the algorithm also uses a heap, map, or auxiliary structure.

Takeaway

Sorting plus greedy is one of the most common algorithmic patterns. The sort arranges decisions so that a local rule becomes meaningful, and the scan commits to choices while preserving an invariant. The essential skill is choosing a sort key that supports an exchange argument. Once that key is found, the implementation is usually a short loop over sorted input.