Buttercola: Facebook: Weighted Interval Scheduling
Facebook: Weighted Interval Scheduling
Given a set of n jobs with [start time, end time, cost], find a subset so that no 2 jobs overlap and the cost is maximum?
A DP Solution:
A DP Solution:
- Sort the intervals by end time.
- Define the DP array
- dp[n + 1], where dp[i] means the the first set non-overlapping of i jobs, save the maximum cost.
- Initial state: dp[0] = 0;
- Transit function:
- dp[i] = Math.max(dp[i - 1], dp[p[i - 1] + 1] + interval[i - 1].cost ), where the p[i - 1] is the index with the end time that is closest to interval[i - 1].end
- Final state: dp[n].
Read full article from Buttercola: Facebook: Weighted Interval Scheduling
No comments:
Post a Comment