Proving Greedy Algorithms Correct

A greedy proof must connect a local decision to an optimal whole solution. Exchange arguments transform an optimum to agree with the greedy prefix; stays-ahead arguments compare prefixes directly; structural induction solves the smaller residual instance after a safe choice. We demonstrate these ideas with shortest-processing-time scheduling: all jobs are available at time zero, run nonpreemptively on one machine, and we minimize the sum of completion times.

Prerequisites: Introduction to Greedy Algorithms; sorting and induction. Related existing lessons: Time Complexity and Big O Notation.

Build the idea

1. State the schedule and objective

   Job i takes positive duration pi and contributes its completion time Ci to the objective. Every job must run exactly once, there are no release dates or precedence constraints, and all jobs have equal weight. Idle time cannot improve completion times, so consider contiguous schedules starting at zero. The algorithm sorts jobs by increasing duration, breaking equal-duration ties by input ID.

2. Compute the cost of an adjacent pair

   Suppose adjacent jobs a,b start after a fixed prefix ending at T. In order a,b, their completion-time sum is 2T+2pa+pb. In order b,a it is 2T+2pb+pa. All later jobs start at the same time after either pair, so their costs are unchanged. The first ordering is no better when pa>pb.

   $$\mathrm{cost}(a,b)-\mathrm{cost}(b,a)=\mathrm{pa}-\mathrm{pb}$$

3. Correctness proof: exchange and induction

   Any duration inversion in an optimal schedule can be swapped without increasing total cost. Repeatedly remove inversions to obtain shortest-first order, proving a greedy optimum exists. Equivalently move a shortest job to the front through safe swaps, then cut away that fixed first job and induct on the residual jobs; adding its duration shifts every later completion by the same constant. This is the cut-and-paste step, not an appeal to intuition.

4. Trace and compare proof styles

   For durations [3,1,2], run IDs 2,3,1, completing at 1,3,6 for total 10. Input order completes at 3,4,6 for total 13. A stays-ahead view observes that the first k shortest durations have minimum prefix completion time among all k-job prefixes. Summing appropriate prefix bounds reaches the same objective. State exactly what stays ahead; a vague claim about being faster is insufficient.

5. Search for counterexamples outside the model

   If jobs have different weights, shortest duration need not minimize weighted completion time; if releases differ, the pair swap may move a job before it exists. These are failures of the proof assumptions. To disprove a proposed rule, enumerate small instances and all permutations, then inspect the first disagreement. Testing can find a counterexample but cannot replace a proof for all legal inputs.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Job{
    long long duration;
    int id;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Job>jobs(n);
    for(int i=0;i<n;++i){
        std::cin>>jobs[i].duration;
        jobs[i].id=i+1;
    }
    std::sort(jobs.begin(),jobs.end(),[](Job a,Job b){
        return a.duration!=b.duration?a.duration<b.duration:a.id<b.id;
    });
    long long clock=0,total=0;
    for(Job j:jobs){
        clock+=j.duration;
        total+=clock;
    } // Each job contributes its completion time.
    std::cout<<total<<'\n';
    for(int i=0;i<n;++i){
        std::cout<<jobs[i].id<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log n) sorting and O(n) accumulation, O(n) job storage. Total completion time is at most 10^6·n(n+1)/2≤5.00005·10^15, fitting long long; individual IDs and n fit int.

Example input and output

Read n (0..100000), then positive integer durations at most 10^6. Print minimum sum of completion times, then job IDs in the chosen execution order. Jobs have release time zero and equal weight.

Input

3
3 1 2

Output

10
2 3 1

Shortest-first produces completion times 1,3,6; swapping each inverted pair cannot increase their sum.

Practical applications

Use adjacent exchanges for ordering objectives, stays-ahead for prefix dominance, and induction after fixing a safe decision. When no proof survives a small change in assumptions, explore DP, search or a different ordering criterion.

Check your understanding

What must an exchange argument show?

Put it into practice

Enumerate every order of four small jobs and compare completion sums.