Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn
Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn
Activity-selection problem Suppose we have a set s= ·· of n proposed activities that wish to use a resource which can be used by only one activity at a time Consider the following set s of activities i12345678910 130535688212 f i 4 67891011121314 Activities a, and a, are compatible if the intervals [s;,A) and si, fi do not overlap
Activity-selection problem Suppose we have a set S = { a 1, a 2, …, a n } of n proposed activities that wish to use a resource which can be used by only one activity at a time. f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Consider the following set S of activities Activities ai and aj are compatible if the intervals [ si, fi ) and [ sj, fj ) do not overlap
Activity-selection problem 1234567891011 s13053|5688|212 f|4567891011121314 Subset (a3, a9, a1 It is not a maximal subset of' mutually compatible activities
Activity-selection problem f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Subset { a 3, a 9, a11 } It is not a maximal subset of mutually compatible activities!
Activity-selection problem 1234567891011 s13053|5688|2 12 f i 4 67891011121314 Subset (a1, a4, ag,a11) It is a largest subset of mutually compatible activities
Activity-selection problem f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Subset { a 1, a 4, a 8, a11 } It is a largest subset of mutually compatible activities
Activity-selection problem 1234567891011 s13053|5688|212 f4567891011121314 Subset (a2, a4, ag,a11) It is a largest subset of mutuall compatible activities too
Activity-selection problem f 4 5 6 7 8 9 10 11 12 13 14 i s 1 3 0 5 3 5 6 8 8 2 12 i i 1 2 3 4 5 6 7 8 9 10 11 Subset { a 2, a 4, a 9, a11 } It is a largest subset of mutually compatible activities too