9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Adam Smith Algorithm Design and Analysis LECTURE 7 • Greedy Algorithms cont’dReview • In a DFS tree of an undirected graph, can there be an edge (u,v) – where v is an ancestor of u? (“back edge”) – where v is a sibling of u? (“cross edge”) • Same questions with a directed graph? • Same questions with a BFS tree – directed? – undirected? 9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Interval Scheduling Problem • Job j starts at sj and finishes at fj. • Two jobs are compatible if they do not overlap. • Find: maximum subset of mutually compatible jobs. 0 1 2 3 4 5 6 7 8 9 10 11 f g h e a b c d Time9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Greedy: Counterexamples for earliest start time for shortest interval for fewest conflictsFormulating Algorithm • Arrays of start and finishing times – s1, s2, …,sn – f1, f2,…, fn • Input length? – 2n = ϴ(n) 9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne • Earliest finish time: ascending order of fj. • Implementation. – Remember job j* that was added last to A. – Job j is compatible with A if sj ≥ fj*. Greedy Algorithm Sort jobs by finish times so that f1 ≤ f2 ≤ ... ≤ fn. A ← φ M Set of selected jobs for j = 1 to n { if (job j compatible with A) A ← A ∪ {j} } return A O(n log n) time; O(n) space.9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Running time: O(n log n) Sort jobs by finish times so that f1 ≤ f2 ≤ ... ≤ fn. A ← (empty) M Queue of selected jobs j* ← 0 for j = 1 to n { if (fj* <= sj) enqueue(j onto A) } return A O(n log n) O(1) n × O(1)9/10/2008 Analysis: Greedy Stays Ahead • Theorem. Greedy algorithm is optimal. • Proof strategy (by contradiction): – Suppose greedy is not optimal. – Consider an optimal strategy… which one? • Consider the optimal strategy that agrees with the greedy strategy for as many initial jobs as possible – Look at first place in list where optimal strategy differs from greedy strategy – Show a new optimal strategy that agrees more w/ greedy A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Analysis: Greedy Stays Ahead • Theorem. Greedy algorithm is optimal. • Pf (by contradiction): Suppose greedy is not optimal. – Let i1, i2, ... ik denote set of jobs selected by greedy. – Let j1, j2, ... jm be set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r. j1 j2 jr i1 i2 ir ir+1 . . . Greedy: OPT: jr+1 why not replace job jr+1 with job ir+1? job ir+1 finishes before jr+19/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Analysis: Greedy Stays Ahead • Theorem. Greedy algorithm is optimal. • Pf (by contradiction): Suppose greedy is not optimal. – Let i1, i2, ... ik denote set of jobs selected by greedy. – Let j1, j2, ... jm be set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r. i1 i2 ir ir+1 Greedy: job ir+1 finishes before jr+1 solution still feasible and optimal, but contradicts maximality of r. j1 j2 jr . . . OPT: ir+19/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Interval Partitioning Problem • Lecture j starts at sj and finishes at fj. • Find: minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room. • E.g.: 10 lectures are scheduled in 4 classrooms. Time 9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 h c b a e d g f i j 3 3:30 4 4:30 1 2 3 49/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Interval Partitioning • Lecture j starts at sj and finishes at fj. • Find: minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room. • E.g.: Same lectures are scheduled in 3 classrooms. Time 9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 h c a e f g i j 3 3:30 4 4:30 d b 1 2 39/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Lower Bound • Definition. The depth of a set of open intervals is the maximum number that contain any given time. • Key observation. Number of classrooms needed ≥ depth. • E.g.: Depth of this schedule = 3 ⇒ this schedule is optimal. • Q: Is it always sufficient to have number of classrooms = depth? a, b, c all contain 9:30 9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 h c a e f g i j 3 3:30 4 4:30 d b 1 2 39/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Greedy Algorithm • Consider lectures in increasing order of start time: assign lecture to any compatible classroom. • Implementation. O(n log n) time; O(n) space. – For each classroom, maintain the finish time of the last job added. – Keep the classrooms in a priority queue (main loop n log(d) time) Sort intervals by starting time so that s1 ≤ s2 ≤ ... ≤ sn. d ← 0 M Number of allocated classrooms for j = 1 to n { if (lecture j is compatible with some classroom k) schedule lecture j in classroom k else allocate a new classroom d + 1 schedule lecture j in classroom d + 1 d ← d + 1 }9/10/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Analysis: Structural Argument • Observation. Greedy algorithm never schedules two incompatible lectures in the same classroom. • Theorem. Greedy algorithm is optimal. • Proof: Let d = number of classrooms allocated by greedy. – Classroom d is opened because we needed to schedule a lecture, say j, that is incompatible with all d-1 last lectures in other classrooms. – These d