COEN 179 Lecture Notes - Lecture 15: Huffman Coding
30 May 2020
School
Department
Course
Professor
Document Summary
Output: a large subset of nonoverlapping intervals: a . Greedy: {g, one of {a, e, f, j, k}, one of {d, m, i, l, m} Theorem: picking the movie with the earliest finish time always yields an optimal solution. Proof: movie(m[]){ if(size == 1) return the only movie m*: movie with least finish time. M": m - (movies overlapping with m*) return (m*) + movie(m"); Claim: there is an optimal solution s for a given set of movies m that includes m*, the movie with earliest finish time. Proof of claim: let s be any optimal solution. If m* is within s, we are done. if not, let be the movie with earliest finish time in s. So m* w s : (cid:8869)# (cid:8869) . Wagoning : m* finishes before so it ends before the start of. # 3 is another sol that includes m* s - { so } t { m.
