Project Completion Time
MediumGreedy · SalesForce
A team must deliver n projects. Each project has two phases:
- Integration by the team lead, taking
integration_times[i]days. The lead can work on only one project at a time, so integrations happen one after another with no gaps. - Development, taking
dev_times[i]days. It starts as soon as that project's integration finishes. There are enough developers that any number of projects can be in development at once, including while the lead integrates other projects.
You may choose the order in which the lead integrates the projects. Work starts on day 0.
Return the earliest day by which every project has finished development. Return 0 if there are no projects.
Example 1
- Input:
- dev_times = [3, 2, 5], integration_times = [2, 2, 1]
- Output:
- 7
- Explanation
- In the given order, integrations end on days 2, 4 and 5, and the last project's 5 days of development finish on day 10. Integrating the 5-day project first instead ends integrations on days 1, 3 and 5, and the projects finish on days 6, 6 and 7.
Example 2
- Input:
- dev_times = [4, 1], integration_times = [3, 6]
- Output:
- 10
- Explanation
- Integrations take 9 days in total whichever order is used. Doing the project with 4 days of development first gives finishes on days 7 and 10, and the other order gives 7 and 13.
Example 3
- Input:
- dev_times = [2, 2, 2], integration_times = [1, 1, 1]
- Output:
- 5
- Explanation
- Integrations end on days 1, 2 and 3, and the last project needs 2 more days, so everything finishes on day 5.
Constraints
dev_times.length==integration_times.length- 0 ≤
n≤ 105 - 0 ≤
dev_times[i],integration_times[i]≤ 104