Design and Analysis of Algorithms

308 Design and Analysis of Algorithms

be polynomial in n and |T |. Assume that a

solution exists.

11.16 An Activity Selection problem is defi ned as

follows: we have a set S = {1, 2, . . . , n} of n

proposed activities that wish to use a resource.

The resource can be used by one activity

at a time. Each activity i has a start time s

i

and a fi nish time f

i

where s

i

≤ f

i

. Activities

are compatible if they do not overlap. Show

that the dynamic programming strategy is

unsuitable for solving this problem.

11.17 An Activity Selection with Profi ts problem

is an extension of the above problem, where

each activity i has, in addition to s

i

and f

i

, a