Greedy Scheduling & Interval Selection

TL;DR — A greedy algorithm makes the locally best choice at each step and never looks back. For some scheduling problems that local choice is provably globally optimal — activity selection (always take the meeting that finishes first) and the min-cost fixed-length window (slide a D-hour window over a cost array, pick the cheapest feasible start). When jobs don't share a resource, per-job greedy = global optimal, proved by an exchange argument. The moment jobs contend for a shared per-hour capacity M, greedy can break, and you fall back to an ascending-slack heuristic or DP.

---

1. Simple explanation

Greedy means: at every step, grab whatever looks best right now, commit to it, and move on. No backtracking, no "what if I'd waited."

That sounds reckless — and often it is. But for certain problems the greedy choice is not just good, it's optimal, because of two properties:

• Greedy-choice property — a globally optimal solution can always start with the locally best move.
• Optimal substructure — after making that move, the rest of the problem is a smaller version of the same problem.

When both hold, greedy wins and it's fast.

Analogy — catching back-to-back movies at a festival. You want to watch as many films as possible in one theater. Films overlap. The winning rule is dead simple: always pick the film that ends earliest among those you can still start. Finishing early frees the room soonest, leaving the most time for everything after. Picking the shortest film, or the one that starts earliest, can lose — a short film in the middle of the day, or an early film that runs till midnight, blocks the room. "Ends earliest" is the greedy choice that provably maximizes the count.

Second flavor of the same idea: you have a deferrable job — say charging an EV. It needs D hours of power, can start no earlier than release, must finish by deadline. Electricity price (or carbon) changes every hour. Greedy answer: slide the D-hour window across its allowed range and start it at the cheapest feasible hour. Same energy is used either way; only when changes.

---

2. Diagram

  ACTIVITY SELECTION (earliest-finish-first)     MIN-COST WINDOW (deferrable job)
  ==========================================     ===============================

  time -->                                       cost array (per hour):
  A  [====]                                       hour:  0   1   2   3   4   5
  B     [======]                                  cost:  9   3   2   8   5   1
  C        [==]                                          .   .   .   .   .   .
  D           [=====]                             job: D = 2 hours, release=1, deadline=5
  E             [===]                                    feasible starts s in [1, 3]
                                                         (need s .. s+D-1 <= deadline-1)
  Sort by FINISH time, sweep left->right:
    take A (ends first)                           window cost(s) = cost[s] + cost[s+1]:
    skip B, C  (overlap A)                          s=1: 3+2 = 5
    take D (first that starts after A ends)          s=2: 2+8 = 10
    skip E (overlaps D)                              s=3: 8+5 = 13
    => {A, D}  = max non-overlapping set                  ^ cheapest feasible = s=1, cost 5

  Greedy choice = "finishes first" / "cheapest    FIFO (carbon-blind) would take s=1 too here,
  window" -> keep it, recurse on the rest.        but in general FIFO takes the EARLIEST start,
                                                   greedy takes the CHEAPEST -> savings.

---

3. How it works

3.1 The greedy paradigm

A greedy algorithm has three moving parts:

You repeat: pick the best feasible candidate, commit, shrink the problem. It only works (gives the optimum) when the two properties in §1 hold. If they don't, greedy is still a fast heuristic — good, not guaranteed.

3.2 Classic interval / activity selection

Given n activities each with (start, finish), choose the largest set with no two overlapping.

Algorithm:

1. Sort activities by finish time ascending. O(n log n).
2. Sweep left to right. Keep a running last_finish (start it at −∞).
3. For each activity, if start ≥ last_finish, take it and set last_finish = finish. Otherwise skip.

The intuition: choosing the earliest-finishing compatible activity always leaves the maximum room for the rest. It is optimal (proof sketch in §3.4).

3.3 The min-cost feasible WINDOW problem

Now a single deferrable job: power P (kW), duration D (hours), earliest start release, must finish by deadline. Cost varies by hour — CI[h] is the cost of hour h.

The carbon (or dollar) cost of starting at hour s is:

cost(s) = Σ_{h=0}^{D-1}  P · CI[s + h]

Same total energy P·D no matter what s is — the job runs the same number of hours. Only which hours differ, so only the when affects cost.

Feasible starts: s ∈ [release, deadline − D]. The quantity slack = deadline − release − D is how much wiggle room the job has. slack = 0 means no choice (one legal start); larger slack means more room to dodge expensive hours.

Greedy: evaluate cost(s) for every feasible s and take the minimum. O(slack · D) naively, or O(deadline − release) with a sliding-window running sum.

3.4 Exchange argument (why per-job greedy is optimal)

Claim: when jobs do not share capacity, picking each job's own min-cost window independently gives the global optimum.

Sketch. Because there's no shared resource, the total cost is just the sum of each job's cost — the jobs are independent. So minimizing the total is the same as minimizing each term separately. Choosing each job's cheapest feasible window therefore minimizes the sum. Done.

The classic exchange argument proves the single-choice rule (e.g. earliest-finish-first): take any optimal solution OPT; if its first activity is not the earliest-finishing one g, swap g in for it. g finishes no later, so it can't conflict with anything OPT scheduled afterward — the swapped solution is still valid and no worse. Repeating, greedy's choices can replace OPT's one by one without loss, so greedy is optimal. The pattern: "greedy's choice can always replace the optimum's first choice without making things worse."

3.5 Where greedy FAILS — shared per-hour capacity

Add a real constraint: at most M kW can run in any single hour. Now jobs contend — if two cheap windows overlap and their combined power exceeds M, they can't both have their first choice. Per-job greedy is no longer optimal, because one job's cheap slot can force a much more expensive slot on another.

Formally the capacity rule is:

for every hour h:   Σ_{jobs j running in h} P_j  ≤  M

This coupling makes the problem hard (it generalizes to NP-hard packing/scheduling in the worst case). Practical responses:

Ascending-slack (a.k.a. earliest-deadline-first / least-slack-first) is the go-to heuristic: jobs with the least freedom get first pick, jobs with lots of slack bend around them.

3.6 Complexity

---

4. The math

Cost of starting a job at hour s (D-hour duration, power P, hourly cost CI):

cost(s) = Σ_{h=0}^{D-1}  P · CI[s + h]

Feasible start set and slack:

s ∈ [release,  deadline − D]
slack = deadline − release − D        (>= 0 required for feasibility)

Greedy (single job):

s* = argmin_{s ∈ [release, deadline−D]}  cost(s)

Savings vs FIFO baseline (FIFO = earliest feasible start, cost-blind):

savings% = (Total_FIFO − Total_greedy) / Total_FIFO × 100

4.1 Worked numeric example

Toy hourly carbon signal (gCO2/kWh), 6 hours:

hour:  0    1    2    3    4    5
CI:   400  120   90  380  250   60

One deferrable job: P = 10 kW, D = 2 h, release = 1, deadline = 5.

Feasible starts: s ∈ [release, deadline − D] = [1, 3]. slack = 5 − 1 − 2 = 2.

Compute cost(s) = 10·(CI[s] + CI[s+1]):

• FIFO takes the earliest feasible start s = 1 → cost 2100.
• Greedy takes the min-cost start s* = 1 → cost 2100.

Here they tie because the cheapest window happens to be the earliest. To see real savings, shift the job to release = 0:

Feasible starts now s ∈ [0, 3]:

• FIFO: earliest start s = 0 → 5200.
• Greedy: min-cost start s = 1 → 2100.

savings% = (5200 − 2100) / 5200 × 100 ≈ 59.6%

Same energy delivered (10 kW · 2 h = 20 kWh), roughly 60% less carbon, purely by choosing when.

---

5. Real code

"""
Greedy scheduling: min-cost window for one job, a FIFO baseline,
and a capacity-aware multi-job scheduler that sorts by ascending slack.
"""
from __future__ import annotations
from dataclasses import dataclass


def min_cost_window(cost, D, release, deadline, P=1.0):
    """Cheapest feasible D-hour start for one job.

    cost[h]  : per-hour cost signal (e.g. carbon intensity).
    D        : job duration in hours.
    release  : earliest legal start hour (inclusive).
    deadline : job must FINISH by this hour, i.e. last used hour is
               deadline-1, so latest start is deadline - D.
    P        : power draw (scales cost; does not change the argmin).

    Returns (best_start, best_cost). Raises if the job cannot fit.
    """
    latest = deadline - D
    if release > latest or D <= 0:
        raise ValueError("infeasible: not enough slack for the job")

    # Sliding-window running sum over D hours -> O(deadline-release).
    window = sum(cost[release:release + D])
    best_start, best_cost = release, window
    for s in range(release + 1, latest + 1):
        window += cost[s + D - 1] - cost[s - 1]   # roll the window forward
        if window < best_cost:
            best_start, best_cost = s, window
    return best_start, P * best_cost


def fifo_start(D, release, deadline):
    """Carbon-blind baseline: earliest feasible start."""
    if release > deadline - D:
        raise ValueError("infeasible")
    return release


@dataclass
class Job:
    name: str
    P: float          # power (kW)
    D: int            # duration (hours)
    release: int
    deadline: int

    @property
    def slack(self) -> int:
        return self.deadline - self.release - self.D


def schedule_all(jobs, cost, M):
    """Capacity-aware greedy: tightest deadline (least slack) goes first.

    Enforces  sum of P over jobs running in any hour <= M.
    Returns {job_name: start_hour}. A job that cannot fit is left unscheduled
    (start = None) rather than violating the cap.
    """
    T = len(cost)
    load = [0.0] * T                       # power already committed per hour
    placement = {}

    # Least-slack-first: jobs with the least freedom pick first.
    for job in sorted(jobs, key=lambda j: (j.slack, j.deadline)):
        latest = job.deadline - job.D
        best_start, best_cost = None, float("inf")
        for s in range(job.release, latest + 1):
            hours = range(s, s + job.D)
            if any(load[h] + job.P > M for h in hours):   # capacity check
                continue
            c = job.P * sum(cost[h] for h in hours)
            if c < best_cost:
                best_start, best_cost = s, c
        placement[job.name] = best_start
        if best_start is not None:                        # commit the load
            for h in range(best_start, best_start + job.D):
                load[h] += job.P
    return placement


if __name__ == "__main__":
    CI = [400, 120, 90, 380, 250, 60]

    # One job, release=0 -> greedy beats FIFO
    s_fifo = fifo_start(D=2, release=0, deadline=5)
    cost_fifo = 10 * (CI[s_fifo] + CI[s_fifo + 1])
    s_greedy, cost_greedy = min_cost_window(CI, D=2, release=0, deadline=5, P=10)
    print("FIFO   start", s_fifo, "cost", cost_fifo)      # start 0 cost 5200
    print("Greedy start", s_greedy, "cost", cost_greedy)  # start 1 cost 2100
    savings = (cost_fifo - cost_greedy) / cost_fifo * 100
    print(f"savings {savings:.1f}%")                      # savings 59.6%

    # Two jobs contending for capacity M
    jobs = [
        Job("A", P=6, D=2, release=0, deadline=6),   # slack 4
        Job("B", P=6, D=2, release=1, deadline=3),   # slack 0 -> picks first
    ]
    print(schedule_all(jobs, CI, M=8))   # B is tightest, reserves its window first

Expected output:

FIFO   start 0 cost 5200
Greedy start 1 cost 2100
savings 59.6%
{'B': 1, 'A': 4}

(With M = 8 kW and each job drawing 6 kW, the two jobs can't share an hour — 6 + 6 = 12 > 8. B has zero slack so it's placed first at its only legal window, hours 1-2. A, with slack to spare, is then pushed to the cheapest window that avoids B's hours, hours 4-5.)

---

6. Real-world example

Scenario: overnight charging for a small EV fleet on a carbon-aware plan.

A depot has 3 EVs to charge overnight. Each needs 2 hours of charging at 10 kW. The grid feeder is limited to M = 20 kW total (so at most 2 chargers at once). Hourly grid carbon over the 6-hour window:

hour:  0    1    2    3    4    5
gCO2:  400  120   90  380  250   60

Jobs (all released at hour 0, all must finish by hour 6, so slack = 4):

The two cheapest 2-hour windows are [1,2] (sum 210) and [4,5] (sum 310). With M = 20, only two chargers fit per hour, so all three can't pile onto the single cheapest window.

Least-slack-first greedy (ties broken by deadline, then order): EV1 takes [1,2] (cost 2100). EV2 also fits [1,2] since 10+10 ≤ 20 (cost 2100). EV3 can't join hour 1 or 2 (would need 30 kW), so it takes the next-cheapest feasible window [4,5] (cost 3100).

Greedy total = 2100 + 2100 + 3100 = 7300 gCO2·(scaled)
FIFO total   = all start at hour 0 as slots free up, cost-blind:
               EV1 [0,1]=5200, EV2 [0,1]=5200, EV3 [2,3]=4700  -> 15100
savings% = (15100 − 7300) / 15100 × 100 ≈ 51.7%

Same 60 kWh delivered to the fleet, roughly half the carbon — achieved by respecting the 20 kW cap and letting the tightest jobs pick first. This is exactly the pattern production carbon-aware and price-aware schedulers use.

---

7. Interview questions companies actually ask

Q1. (Google / Amazon) Activity selection — maximize non-overlapping intervals. What's the greedy rule and why? Sort by finish time, then greedily take each activity whose start is ≥ the last taken finish. Earliest-finish-first is optimal because finishing soonest leaves the most room for future activities; an exchange argument shows any optimal solution's first pick can be swapped for the earliest-finishing one without conflict or loss. O(n log n).

Q2. (LeetCode 253) Meeting Rooms II — minimum rooms for all meetings. This is not the selection problem; you must schedule everything with the fewest rooms. Sort start and end times separately (or use a min-heap of end times). Sweep events: on a start, if the earliest-ending room is free (its end ≤ current start) reuse it, else open a new room. The peak number of simultaneous meetings is the answer. O(n log n).

Q3. (LeetCode 621) Task Scheduler — min intervals with cooldown n between identical tasks. Greedy on the most frequent task: it dictates the frame. With fmax = max frequency and cnt tasks tied at that max, the answer is max(len(tasks), (fmax − 1)·(n + 1) + cnt). The formula fills idle slots with other tasks; if there are enough tasks to fill every gap, no idling is needed.

Q4. "Minimize total cost of scheduling deferrable jobs under a time-varying cost signal." Approach? If jobs don't share a resource: for each job independently, slide its fixed-length window over the cost array within [release, deadline−D] and pick the cheapest feasible start — per-job optimal is globally optimal by an exchange/independence argument. If jobs share a per-hour capacity M, they contend; use least-slack-first (earliest-deadline-first) greedy as a heuristic, or DP/ILP for an exact optimum on small instances.

Q5. When does greedy give the optimal answer, and how do you prove it? When the problem has the greedy-choice property (an optimum can start with the local best move) and optimal substructure (the remainder is the same problem, smaller). You prove it with an exchange argument: show the greedy first choice can replace the optimum's first choice without making the solution worse, then induct.

Q6. Give a case where greedy fails. 0/1 knapsack: greedily taking the highest value-per-weight item can be suboptimal because you can't take fractions — you might leave capacity that a different combination would have used better. Coin change with arbitrary denominations (e.g. coins {1,3,4}, target 6) also breaks greedy (greedy gives 4+1+1=3 coins, optimal is 3+3=2). These need DP.

Q7. Complexity of the min-cost window, and how to speed it up? Naively O(slack · D) if you re-sum each window. Use a sliding-window running sum (add the entering hour, subtract the leaving hour) to get O(deadline − release). A prefix-sum array gives O(1) per window query after O(T) preprocessing.

Q8. Why is least-slack-first a reasonable heuristic under shared capacity? Jobs with the least slack have the fewest legal placements, so scheduling them first avoids painting yourself into a corner where a tight job has no feasible slot left. It mirrors earliest-deadline-first, which is optimal for single-machine feasibility; under capacity it's not provably optimal but performs well and is cheap.

Q9. FIFO vs greedy — how do you quantify the win? FIFO starts each job at its earliest feasible hour, ignoring cost. Greedy starts at the cheapest feasible hour. Report savings% = (Total_FIFO − Total_greedy)/Total_FIFO × 100. Both deliver identical energy (P·D); the delta is purely from when the work runs.

---

8. When to use / tradeoffs

Reach for greedy scheduling when:

• The problem has greedy-choice + optimal-substructure (activity selection, single min-cost window).
• Jobs are independent (no shared resource) — per-job greedy is then globally optimal.
• You need speed and a simple, explainable rule (O(n log n)).

Do NOT rely on greedy when:

Honest limits: least-slack-first is a heuristic under capacity — it's fast and usually good but can be suboptimal, so validate against DP on small instances if optimality matters. And greedy gives one answer with no easy "second best," so if you need robustness to changing forecasts (e.g. uncertain future carbon), consider re-optimizing on a rolling horizon rather than committing everything up front.

---

9. Summary + related articles

• Greedy = commit to the locally best choice; optimal only when greedy-choice + optimal-substructure hold.
• Activity selection: sort by finish time, take earliest-finishing compatible interval — optimal by exchange argument.
• Min-cost window: slide a D-hour window over the cost array, pick the cheapest feasible start in [release, deadline−D].
• Independent jobs → per-job greedy is globally optimal; a shared per-hour cap M creates contention → use ascending-slack (earliest-deadline-first) or DP.
• Quantify against FIFO with savings% = (Total_FIFO − Total_greedy)/Total_FIFO × 100; same energy, different when.

Related:

• Scheduling Under a Time-Varying Cost Signal
• Carbon-Aware Scheduling of Flexible Loads
• Dynamic Programming
• Weighted Averages & Aggregation

Resources

• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), Ch. 16 "Greedy Algorithms" (activity selection, exchange arguments).
• Kleinberg & Tardos — Algorithm Design, Ch. 4 "Greedy Algorithms" (interval scheduling, exchange proofs).
• LeetCode: Meeting Rooms II (253), Task Scheduler (621), Non-overlapping Intervals (435) — https://leetcode.com/
• Earliest-deadline-first scheduling — https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling