interval scheduling :
maximum no of task can be done without overlap question- https://cses.fi/problemset/task/1629
SORT order Creteria :
- input order
- start time
- finsih time
- total time
- min conflicts
PROOF:
Compare the set of G of requests selected by greedy to a hypothetical set H of requests that give optimal answr. G= {} H={} we want to show k >= l.
lemma : i ⇐k ⇒ ( because we sorted according to finsish time)
base case : i =1
greedy always chooses g1 minimum from set thats that <
ssume:
f(gi)≤f(hi)f(g_i) \le f(h_i)f(gi)≤f(hi)
We want to show:
f(gi+1)≤f(hi+1)f(g_{i+1}) \le f(h_{i+1})f(gi+1)≤f(hi+1)
Why this is true:
- Since greedy picked g1,…,gig_1, \ldots, g_ig1,…,gi, the next interval greedy can choose must start after:
s(gi+1)≥f(gi)s(g_{i+1}) \ge f(g_i)s(gi+1)≥f(gi)
- By the inductive hypothesis:
f(gi)≤f(hi)f(g_i) \le f(h_i)f(gi)≤f(hi)
- Because the intervals in HHH do not overlap, we also have:
s(hi+1)≥f(hi)s(h_{i+1}) \ge f(h_i)s(hi+1)≥f(hi)
Thus:
s(hi+1)≥f(hi)≥f(gi)s(h_{i+1}) \ge f(h_i) \ge f(g_i)s(hi+1)≥f(hi)≥f(gi)
This means:
➡️ hi+1h_{i+1}hi+1 is a valid candidate interval for greedy at step i+1i+1i+1
(its start time is after the finish time of all g1,…,gig_1,\ldots, g_ig1,…,gi).
Greedy picks the interval with minimum finish time among all valid candidates.
So:
f(gi+1)≤f(hi+1)f(g_{i+1}) \le f(h_{i+1})f(gi+1)≤f(hi+1)