(b) (5%) f(x; θ) = 1 / θ, 0 &lt; x &lt; θ &lt; ∞

1. We have n activities \( a1, a2, \ldots, an \). Each activity \( ai \) has a start time \( si \) and a finish time \( fi \) where \( 0 \leq si < fi \). If \( ai \) is selected, activity \( ai \) takes place during the half-open time interval \( [si, fi] \). Activities \( ai \) and \( aj \) are compatible if the intervals \( [si, fi] \) and \( [sj, fj] \) do not overlap. In the Activity Selection Problem, we try to select a maximum-size subset of mutually compatible activities. Design an O(nlog n)-time algorithm to solve this problem. (15分)

題組內容

(b) \( (5\%) f(x; \theta) = 1 / \theta, 0 < x < \theta < \infty \)

相關申論題

相關試卷