Chapter 1: Introduction to Interval Scheduling and Complexity

Source files used: Intro_ocw (Lecture 1 notes), Matrix Multiplication (Recitation 1, Section 1 only), MIT6_046JS15_pset1 (Problem 1-1 as practice). No worked examples are included.

1. Big Picture

The first lecture is about one idea: very similar problems can have very different complexity.

The lectures show this with one family of scheduling problems:

• unweighted interval scheduling: a simple greedy algorithm is optimal,
• weighted interval scheduling: greedy fails, dynamic programming works in $O(n\lg n)$,
• interval scheduling on non-identical machines: NP-complete.

$$\boxed{\text{Classify the problem, then pick greedy, DP, or "deal with intractability".}}$$

The course modules that follow: divide and conquer (FFT, randomized algorithms), optimization (greedy, dynamic programming), network flow, intractability, linear programming, sublinear and approximation algorithms, advanced topics. The prerequisite is 6.006 material: heaps, trees, graphs, sorting, shortest paths, graph search, dynamic programming.

---

2. Core Ideas

2.1 P, NP, NP-Complete

P: problems solvable in polynomial time, $O(n^k)$ for some constant $k$ (shortest paths, $O(V^2)$).

NP: problems whose solutions can be verified in polynomial time.

NP-complete: in NP, and as hard as any problem in NP.

$P\subseteq NP$. Whether $P=NP$ is open. If any NP-complete problem has a polynomial-time solution, then every problem in NP does.

Example from the lectures: deciding whether a directed graph has a Hamiltonian cycle (a simple cycle through every vertex) is NP-complete, but verifying that a given cycle is Hamiltonian is easy.

---

2.2 Interval Scheduling Setup

Requests $1,\dots,n$ share a single resource. Request $i$ has start time $s(i)$ and finish time $f(i)$, with $s(i)<f(i)$.

Two requests $i$ and $j$ are compatible if they do not overlap:

$$f(i)\le s(j)\quad\text{or}\quad f(j)\le s(i)$$

Goal: select a compatible subset of maximum size.

---

2.3 Greedy Algorithms

A greedy algorithm is myopic: it processes the input one piece at a time with no apparent look-ahead.

Greedy template for interval scheduling:

1. Use a simple rule to select a request $i$.
2. Reject all requests incompatible with $i$.
3. Repeat until all requests are processed.

The whole question is which rule. Only one of the four candidate rules works (Section 5.1).

---

2.4 Why Greedy Breaks with Weights

Each request now has a weight $w(i)$, and the goal is a compatible subset of maximum total weight.

Lecture counterexample: two short requests with $w=1$ each and one overlapping request with $w=3$. Earliest finish time picks the two $w=1$ requests (total 2) instead of the single $w=3$ request. Greedy no longer works; use dynamic programming.

---

2.5 Dynamic Programming by Guessing

Subproblems are suffixes of time:

$$R^x=\{\,j\in R \mid s(j)\ge x\,\}$$

If $x=f(i)$, then $R^x$ is the set of requests that start after request $i$ finishes. There are $n$ different subproblems, one per request. Solve each once and memoize.

Guess: try each request $i$ as the first request. Then the remaining requests are $R^{f(i)}$. Some requests compatible with $i$ may not be in $R^{f(i)}$, but that is fine because $i$ is being picked as the first one (requests are taken in order).

---

2.6 Dealing with Intractability

When a problem is NP-hard, the lectures list three options:

• Approximation algorithms: guaranteed within some factor of optimal, in polynomial time.
• Pruning heuristics: reduce a (possibly exponential) runtime on real-world inputs.
• Greedy or other suboptimal heuristics: work well in practice, no guarantees.

---

3. Main Governing Equations and Formulas

3.1 Compatibility Condition

$$f(i)\le s(j)\quad\text{or}\quad f(j)\le s(i)$$

Use to decide whether two requests can both be scheduled. Touching endpoints ($f(i)=s(j)$) count as compatible.

---

3.2 Greedy Output Structure (Claim 1)

Earliest-finish-time greedy outputs intervals $\langle s(i_1),f(i_1)\rangle,\dots,\langle s(i_k),f(i_k)\rangle$ with

$$s(i_1)<f(i_1)\le s(i_2)<f(i_2)\le\cdots\le s(i_k)<f(i_k)$$

Proof: if $f(i_j)>s(i_{j+1})$, intervals $j$ and $j+1$ intersect, which contradicts step 2 of the algorithm (incompatible requests were rejected).

Use to argue the greedy output is a valid (compatible) schedule.

---

3.3 Greedy Optimality (Claim 2)

Given a list of intervals $L$, greedy with earliest finish time produces $k^*$ intervals, where $k^*$ is optimal.

Proof is by induction on $k^*$. The key exchange step: greedy’s first interval finishes no later than the optimal schedule’s first interval,

$$f(i_1)\le f(j_1)$$

so swapping $j_1$ for $i_1$ in the optimal schedule keeps it valid and optimal. The full proof is in the Induction guide (Section 3.4 there).

Use when asked to prove a greedy rule is optimal.

---

3.4 Weighted Interval Scheduling: Lecture Recurrence

$$\text{opt}(R)=\max_{1\le i\le n}\Big(w_i+\text{opt}\big(R^{f(i)}\big)\Big)$$

Running time: $O(n^2)$ ($n$ subproblems, $O(n)$ choices each).

Use as the DP definition when the problem is weighted.

---

3.5 Weighted Interval Scheduling: Recitation $O(n\lg n)$ Version

Sort requests by finish time:

$$f(1)\le f(2)\le\cdots\le f(n)$$

Define $p(j)$ as the largest index $i<j$ such that requests $i$ and $j$ are compatible. $M[k]$ is the maximum weight using requests $1$ to $k$.

$$M[0]=0,\qquad M[j]=\max\big(w(j)+M[p(j)],\;M[j-1]\big)$$

M[0] = 0
for j = 1 to n
    M[j] = max(w(j) + M[p(j)], M[j-1])

Costs: sorting $O(n\log n)$, filling $M$ is $O(n)$, tracing back the chosen set $O(n)$. Total $O(n\log n)$.

Use this version when the question asks for the fastest algorithm. The two branches of the max are “take $j$” and “skip $j$“.

---

3.6 Non-Identical Machines

Requests $1,\dots,n$ with $s(i)$, $f(i)$ as before, weight 1 each. There are $m$ machine types $\mathcal{T}=\{T_1,\dots,T_m\}$, and $Q(i)\subseteq\mathcal{T}$ is the set of machines request $i$ can run on. Goal: maximize the number of jobs scheduled on the $m$ machines.

• In NP: any given subset of jobs with machine assignments can be checked for legality.
• Decision version (“can $k\le n$ requests be scheduled?”): NP-complete.
• Maximization version: NP-hard.

Use as the lecture’s example of a small change to the problem that makes it intractable.

---

4. Problem-Solving Workflow

4.1 Designing an Algorithm (Problem Set Format)

The problem sets ask for a short essay, not just code:

1. Define the problem and state your result.
2. Describe the algorithm in English (pseudocode if helpful).
3. Prove correctness (or give a proof sketch).
4. Analyze the running time.

Full credit requires a correct solution that is clearly described.

4.2 Attacking a Scheduling-Type Problem

1. Check whether a greedy rule could work. Try to break each candidate rule with a small counterexample (Section 5.1).
2. If one rule survives, prove it: show the output is valid (Section 3.2), then prove optimality by induction plus an exchange argument (Section 3.3).
3. If weights or other structure break greedy, define DP subproblems (Section 2.5) and a recurrence (Section 3.4).
4. Speed up the DP with sorting and $p(j)$ (Section 3.5).
5. If even small variants look hard, check membership in NP and think about NP-completeness (Section 3.6), then pick a way to deal with intractability (Section 2.6).

Practice: Problem Set 1, Problem 1-1 (restaurant placement on a tree) follows exactly this path: break a greedy rule with a counterexample, design an efficient algorithm on trees, prove a simple greedy for the equal-profit case, then consider arbitrary graphs.

---

5. Decision Rules / Decision Trees

5.1 Which Greedy Rule?

Earliest start time (min $s(i)$)? → fails: one long request that starts first blocks several short ones

Shortest request (min $f(i)-s(i)$)? → fails: a short request can overlap two longer compatible ones

Fewest incompatibilities? → fails: the lecture gives a layered counterexample

Earliest finish time (min $f(i)$)? → optimal

5.2 Greedy or DP?

Unweighted, maximize the count? → greedy, earliest finish time

Weighted, maximize total weight? → DP: $M[j]=\max(w(j)+M[p(j)],M[j-1])$

Requests restricted to machine subsets $Q(i)$? → NP-complete decision version, NP-hard optimization

5.3 Class of a Problem

Can you solve it in $O(n^k)$? → in P

Can you only verify a proposed answer in polynomial time? → in NP

In NP AND as hard as every NP problem? → NP-complete

---

6. Important Tables / Correlations Needed

6.1 Interval Scheduling Variants

Variant	Method	Time
Unweighted, one resource	greedy, earliest finish time	sort, then one scan
Weighted, lecture DP	$\text{opt}(R)=\max_i(w_i+\text{opt}(R^{f(i)}))$	$O(n^2)$
Weighted, recitation DP	sort by $f$, use $p(j)$ and $M[j]$	$O(n\log n)$
Non-identical machines	none known in poly time	NP-complete / NP-hard

6.2 Complexity Classes

Class	Meaning	Lecture example
P	solvable in polynomial time	shortest paths
NP	verifiable in polynomial time	checking a Hamiltonian cycle
NP-complete	in NP and as hard as any NP problem	Hamiltonian cycle existence
NP-hard	at least as hard as NP-complete (optimization form)	max jobs on non-identical machines

---

7. Key Takeaways

• Very similar problems can have very different complexity.
• Two requests are compatible if $f(i)\le s(j)$ or $f(j)\le s(i)$.
• Earliest finish time is the only one of the four greedy rules that is optimal.
• Greedy optimality is proved by induction on $k^*$ with the exchange fact $f(i_1)\le f(j_1)$.
• Weights break greedy; use DP over subproblems $R^{f(i)}$.
• Lecture DP is $O(n^2)$; sorting by finish time and $p(j)$ gives $O(n\log n)$.
• $M[j]=\max(w(j)+M[p(j)],M[j-1])$: take $j$ or skip $j$.
• P $\subseteq$ NP; if any NP-complete problem is in P, then P = NP.
• Scheduling on non-identical machines is NP-complete (decision) and NP-hard (maximize).
• For intractable problems: approximation, pruning heuristics, or heuristics with no guarantee.