Frontend School

Maximize Project Value with Flexible Deadlines

DSA
hard

Maximize Project Value with Flexible Deadlines

Hard
Greedy
Disjoint Set Union
coordinate-compression
Sorting

Overview

You are a project manager tasked with maximizing the total value of projects completed within a tight schedule. Each project has a specific window of days during which it can be undertaken, and a corresponding profit. You have a single resource, meaning only one project can be worked on during any given day. This problem challenges your ability to apply greedy algorithms and efficient data structures to navigate scheduling complexities and achieve optimal outcomes.

What you need to do / Task

Implement the maximizeProjectValue function. This function should determine the maximum total profit achievable by selecting a subset of projects, such that each selected project is completed on exactly one day within its allowed [startDay, endDay] window, and no two selected projects are completed on the same day.

Input & output

Input: projects: An array of Project objects. Each Project object has the following properties:

  • startDay: A number representing the earliest day the project can be started (inclusive).
  • endDay: A number representing the latest day the project can be completed (inclusive).
  • profit: A number representing the profit gained if the project is completed.

Output: A number representing the maximum total profit that can be achieved.

Clarifications

  • Empty Input: If the projects array is empty, the function should return 0.
  • Overlapping Windows: Projects may have overlapping [startDay, endDay] windows. Your solution must ensure that no two selected projects are assigned to the same day.
  • Large Day Numbers: startDay and endDay can be very large, up to 10^9. Your solution should handle this efficiently without creating excessively large data structures indexed by day.
  • Profit Sum: The total profit can be very large, potentially exceeding the capacity of a 32-bit integer. Use a data type that can accommodate sums up to N * max_profit (e.g., long in Java/C++, number in TypeScript/JavaScript).

Examples

1

Example 1

Input:

projects = [ { startDay: 1, endDay: 2, profit: 10 }, { startDay: 1, endDay: 1, profit: 5 }, { startDay: 2, endDay: 2, profit: 15 } ]

Output:

25

Note:

Projects sorted by profit (descending): P3(2,2,15), P1(1,2,10), P2(1,1,5).

  1. Schedule P3 (profit 15) on day 2 (latest possible day in [2,2]). Total profit = 15. Day 2 is taken.
  2. Schedule P1 (profit 10) on day 1 (latest possible day in [1,2] that is free). Total profit = 15 + 10 = 25. Day 1 is taken.
  3. P2 (profit 5) cannot be scheduled as day 1 is taken and its window is [1,1]. Maximum profit is 25.
2

Example 2

Input:

projects = [ { startDay: 1, endDay: 5, profit: 100 }, { startDay: 2, endDay: 3, profit: 10 }, { startDay: 4, endDay: 6, profit: 50 } ]

Output:

160

Note:

Projects sorted by profit (descending): P1(1,5,100), P3(4,6,50), P2(2,3,10).

  1. Schedule P1 (profit 100) on day 5 (latest possible day in [1,5]). Total profit = 100. Day 5 is taken.
  2. Schedule P3 (profit 50) on day 6 (latest possible day in [4,6]). Total profit = 100 + 50 = 150. Day 6 is taken.
  3. Schedule P2 (profit 10) on day 3 (latest possible day in [2,3]). Total profit = 150 + 10 = 160. Day 3 is taken. Maximum profit is 160.
3

Example 3

Input:

projects = [ { startDay: 10, endDay: 20, profit: 30 }, { startDay: 15, endDay: 25, profit: 40 }, { startDay: 5, endDay: 12, profit: 20 } ]

Output:

90

Note:

Projects sorted by profit (descending): P2(15,25,40), P1(10,20,30), P3(5,12,20).

  1. Schedule P2 (profit 40) on day 25 (latest possible day in [15,25]). Total profit = 40. Day 25 is taken.
  2. Schedule P1 (profit 30) on day 20 (latest possible day in [10,20]). Total profit = 40 + 30 = 70. Day 20 is taken.
  3. Schedule P3 (profit 20) on day 12 (latest possible day in [5,12]). Total profit = 70 + 20 = 90. Day 12 is taken. Maximum profit is 90.

Constraints

Constraints & assumptions

  • 1 <= projects.length <= 10^5 (denoted as N)
  • 1 <= project.startDay <= project.endDay <= 10^9
  • 1 <= project.profit <= 10^9
  • Time complexity: O(N log N)
  • Space complexity: O(N)

Out of scope

  • Error handling for invalid input types or negative values.
  • Parallel project execution or multi-resource scheduling.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly applies a greedy strategy to maximize total profit.
  • Data Structure Efficiency: Optimal use of data structures to handle large day ranges and N operations efficiently.
  • Complexity Analysis: Ability to clearly articulate the time and space complexity of the solution.
  • Code Quality: Clean, readable, and well-structured code with appropriate variable names.

Loading editor...