k****r
发帖数: 807 | 2 1. sort based on end
2. dp calculate the cost from the 1st to the last.
DP function:
for (int i = 1; i < n; i++) {
int idx = LastNonoverlopJob(input, i);
dp[i] = Math.max(dp[i - 1], idx == -1 ? input[i].profit : (dp[idx] +
input[i].profit));
}
where LastNonoverlopJob can be realized by binary search.
Any better idea? |
