Problem
Each project is [start_day, end_day, reward]. It occupies every day from start_day through end_day, including both endpoints. You can participate in only one project on a day. Choose a subset with the largest total reward. A project starting on another project’s end day conflicts with it.
Implement project_rewards(projects).
Input
projects: Rows of three integers: start day, end day, and reward.
Output
Return the maximum total reward; the chosen projects need not be returned.
Constraints
1 ≤ projects ≤ 200,000. 1 ≤ start_day ≤ end_day ≤ 1,000,000,000. Rewards are positive integers at most 1,000,000,000.
Examples
Input:
projects = [
[1, 2, 4],
[3, 4, 5],
[2, 3, 10]
]
Expected output:
expected = 10Input:
std::vector<std::vector<long long>> projects = {
{1, 2, 4},
{3, 4, 5},
{2, 3, 10}
};
Expected output:
long long expected = 10;Input:
long[][] projects = new long[][] {
new long[] {1, 2, 4},
new long[] {3, 4, 5},
new long[] {2, 3, 10}
};
Expected output:
long expected = 10;Explanation
The first two projects earn 9 together. The last earns 10 and conflicts with both, so choose it alone.
Input:
projects = [
[1, 2, 4],
[2, 3, 5]
]
Expected output:
expected = 5Input:
std::vector<std::vector<long long>> projects = {
{1, 2, 4},
{2, 3, 5}
};
Expected output:
long long expected = 5;Input:
long[][] projects = new long[][] {
new long[] {1, 2, 4},
new long[] {2, 3, 5}
};
Expected output:
long expected = 5;Explanation
Both occupy day 2. Choose only the second, with reward 5.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
This is a weighted interval scheduling problem with overlapping time ranges.
Hint 2
Sort projects by end day and combine each project with the latest compatible earlier one.
Hint 3
Be precise about conflicts: another project starting on an end day still overlaps.
Expected complexity
O(n log n) time, O(n) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.