Question 11 Solution
COMP3121/9101 21T3 Final Exam
Copyright By PowCoder代写 加微信 powcoder
This document gives a model solution to question 11 of the final exam. Note that alter-
native solutions may exist.
1. You are given n intervals on an axis. The ith interval [li, ri) has integer endpoints
li < ri and has a score of si. Your task is to select a set of disjoint intervals with
maximum total score. Note that if intervals i and j satisfy ri = lj then they are still
Design an algorithm which solves this problem and runs in O(n2) time.
You must provide reasoning to justify the correctness and time complexity of your
algorithm.
The input consists of the positive integer n, as well as 2n integers l1, r1, . . . , ln, rn and
n positive real numbers s1, . . . , sn.
The output is the set of intervals chosen, organised in any format or data structure.
For example, if n = 4 and the intervals are:
l1 = 0 r1 = 3 s1 = 2
l2 = 1 r2 = 3 s2 = 1
l3 = 2 r3 = 4 s3 = 4
l4 = 3 r4 = 5 s4 = 3
then you should select only the first and fourth intervals, for a maximum total score
of 5. Note that interval 3 is not disjoint with any other interval.
Sort the intervals by increasing order of endpoint ri and relabel accordingly. Hence-
forth we assume r1 ≤ . . . ≤ rn.
We then proceed by dynamic programming.
Subproblems: for 0 ≤ i ≤ n, let P (i) be the problem of determining opt(i), the
maximum total score of a set of disjoint intervals where the last chosen interval is the
ith, and m(i), the second largest interval index in one such set. If the set consists of
only one interval, then m(i) will be zero.
Recurrence: for 1 ≤ i ≤ n,
m(i) = argmax
opt(i) = si + opt(m(i)).
The solution for i must include interval i, so we extend the best solution with last
chosen interval j finishing at or before the start of interval i.
Base case: opt(0) = 0 and m(0) is undefined.
Order of computation: subproblem P (i) depends only on earlier subproblems (P (j),
where j < i), so we can solve the subproblems in increasing order of i.
Final answer: The maximum total score is
To recover the set which yields this score, we let
i∗ = argmax
and backtrack through the m array to obtain the set {i∗,m(i∗),m(m(i∗)), . . .}.
Time complexity: There are O(n) subproblems, each solved in O(n), and constructing
the final answer also takes O(n). Thus the overall time complexity is O(n2).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com