Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

2. A Scheduling Problem

  • Advanced Algorithms
    • Flows
    • Intractability
    • Approximation Algorithms
    • Randomized Algorithms
    • Greedy Algorithms
      • 1. Storing Files on a Tape
      • 2. A Scheduling Problem
      • 3. Stable Matchings
    • Matroids
      • 1. The Motivation
      • 2. The Definition
      • 3. Greedy Works!
      • 4. Scheduling with Deadlines
    • Dynamic Programming
      • 1. Longest Increasing Subsequence
      • 2. Subset Sum
      • 3. Set Cover
      • 4. Optimal BSTs
      • 5. Maximum Independent Set on Trees

On this page

  • The Problem
  • Greedy Works Out
  • General Patterns

2. A Scheduling Problem

algonotes
lecturenotes
Published

May 16, 2023

Acknowledgements

This write up is borrowed (with minor adaptations) from Chapter 4 of Jeff Erickson’s textbook on Algorithms.

The Problem

Suppose you decide to sign up for dance classes, and a dance academy next door offers a bunch of classes, but only on Saturdays. You cannot take two classes whose timings overlap: for example, in the example shown in the figure below, the Bollywood and Ballet classes are clashing, so you would have to pick one between the two.

More formally:

  • Suppose you are given two arrays S[1..n]S[1 .. n]S[1..n] and F[1..n]F[1 .. n]F[1..n] listing the start and finish times of each class; to be concrete, we can assume that 0≤S[i]<F[i]≤M0 \leq S[i]<F[i] \leq M0≤S[i]<F[i]≤M for each iii, for some value MMM.
  • Your task is to choose the largest possible subset X∈{1,2,…,n}X \in\{1,2, \ldots, n\}X∈{1,2,…,n} so that for any pair i,j∈Xi, j \in Xi,j∈X, either S[i]>F[j]S[i]>F[j]S[i]>F[j] or S[j]>F[i]S[j]>F[i]S[j]>F[i].

We can illustrate the problem by drawing each class as a rectangle whose left and right xxx-coordinates show the start and finish times. The goal is to find a largest subset of rectangles that do not overlap vertically, as shown below1.

Notice that there are several natural greedy approaches to this problem. A template for a greedy algorithm would look like this:

repeat while there is at least one class left:
- pick a class, say C, that is <<GREEDY CHOICE>>
- eliminate C and all classes that clash with C from the collection

Here are some “natural” greedy choices:

  • pick a class that has the shortest duration
  • pick a class that has the fewest clashes with other classes
  • pick a class that starts as early as possible
  • pick a class that finishes as early as possible
Greedy Does Not Work!

It turns out that the first three greedy approaches are actually wrong, in the sense that there are examples on which they will fail to produce an optimal schedule. Can you construct these examples?

The intuition for the last option above is that we would like the first class to finish as early as possible, because that leaves us with the largest number of remaining classes. This intuition suggests the following simple greedy algorithm. Scan through the classes in order of finish time; whenever you encounter a class that doesn’t conflict with your latest class so far, take it! Here is some pseudocode that captures this process:

GreedySchedule(S,F)

sort F and permute S to match 
count = 1
X[count] = 1

for i from 2...n:
    if S[i]>F[X[count]]
        count = count +1
        X[count] = i
return X[1...count]

A greedy algorithm for finding a maximum set of non-overlapping classes

Greedy Works Out

To prove that GreedySchedule actually computes the largest conflict-free schedule, we use an exchange argument, similar to the one we used for tape sorting. We are not claiming that the greedy schedule is the only maximal schedule; there could be others. (Can you come with examples to justify this comment?)

All we can claim is that at least one of the optimal schedules is the one produced by the greedy algorithm.

At least one maximal conflict-free schedule includes the class that finishes first.

Proof: Let fff be the class that finishes first. Suppose we have a maximal conflict-free schedule XXX that does not include fff. Let ggg be the first class in XXX to finish. Since fff finishes before ggg does, fff cannot conflict with any class in the set X\{g}X \backslash\{g\}X\{g}. Thus, the schedule X′=X∪{f}\{g}X^{\prime}=X \cup\{f\} \backslash\{g\}X′=X∪{f}\{g} is also conflict-free. Since X′X^{\prime}X′ has the same size as XXX, it is also maximal.

To finish the proof, we call on our old friend induction.

Theorem. The greedy schedule is an optimal schedule.

Proof: Let fff be the class that finishes first, and let AAA be the subset of classes that start after fff finishes. The previous lemma implies that some optimal schedule contains fff, so the best schedule that contains fff is an optimal schedule. The best schedule that includes fff must contain an optimal schedule for the classes that do not conflict with fff, that is, an optimal schedule for AAA. The greedy algorithm chooses fff and then, by the inductive hypothesis, computes an optimal schedule of classes from AAA.

Another way to see why greedy works is the following. Consider the finish times of all the greedy choices. Note that every other class contains at least one of these finish times: if not, then there is a class that starts after the ithi^{th}ith earliest class to start (among the greedy choices) and finishes before the (i+1)th(i+1)^{th}(i+1)th earliest class to start (among the greedy choices). This means that the choice made by the greedy algorithm in the (i+1)th(i+1)^{th}(i+1)th step was not on brand: a contradiction.

Why is this observation useful? Well, suppose the greedy algorithm outputs a collection of kkk classes. Then define the following groups of classes: — the jjj-th group consists of all classes that are active during the finish time of the jthj^{th}jth earliest class to start among the greedy chocies. These groups form a cover, i.e, every class belongs to at least one of these groups because of our observation earlier. Now notice that all classes within any group are mutually clashing, because they are all active at a common time. Therefore, any valid solution cannot pick more than one class from a given group, implying therefore that any solution must have at most kkk classes. But the greedy outcome has exactly kkk classes, so this is indeed the best we can hope for.

General Patterns

The basic structure of this correctness proof is exactly the same as for the tape-sorting problem: an inductive exchange argument.

  • Assume that there is an optimal solution that is different from the greedy solution.

  • Find the “first” difference between the two solutions. - Argue that we can exchange the optimal choice for the greedy choice without making the solution worse (although the exchange might not make it better).

This argument implies by induction that some optimal solution contains the entire greedy solution, and therefore equals the greedy solution. Sometimes, as in the scheduling problem, an additional step is required to show no optimal solution strictly improves the greedy solution.

Footnotes

  1. Why is this optimal?↩︎


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×