Frontend School

Maximized Profit from Concurrent Project Selection

DSA
hard

Maximized Profit from Concurrent Project Selection

Hard
Greedy
Priority Queue
Intervals

Overview

You are an operations manager at a consulting firm tasked with optimizing project assignments. Your firm has a limited number of consultants (or slots) who can work on projects simultaneously. Each project has a defined start and end time, along with an associated profit. Your goal is to select a subset of projects to maximize the total profit, adhering to the constraint that at most K projects can run concurrently at any given moment.

This problem is crucial for resource allocation and maximizing revenue in a capacity-constrained environment. Efficiently solving it requires careful consideration of project timelines and profitability.

What you need to do / Task

Implement the maximizeProfit function which takes a list of projects and an integer K (maximum concurrent projects) as input. The function should return the maximum total profit achievable by selecting projects under the given constraint.

Deliverables:

  1. Implement the maximizeProfit function.
  2. Ensure your solution correctly handles overlapping projects and the K concurrency limit.
  3. Your solution should be optimized for time and space complexity.

Input & output

  • Input:
    • projects: An array of arrays, where each inner array [start_time, end_time, profit] represents a project. start_time, end_time, and profit are positive integers.
    • K: An integer representing the maximum number of projects that can run concurrently. K will always be a positive integer.
  • Output:
    • A single integer representing the maximum total profit achievable.

Clarifications

  • Projects are considered to be running from start_time up to, but not including, end_time. That is, [s1, e1, p1] and [s2, e2, p2] are considered concurrent if their intervals [s1, e1) and [s2, e2) overlap. A project ending at t frees up its slot at time t. A project starting at t occupies a slot from time t.
  • Projects can have the same start times or end times.
  • K will always be at least 1.

Examples

1

Example 1

Input:

projects = [[1,5,10], [2,7,15], [6,10,12]], K = 2

Output:

37

Note:

Projects: P1=[1,5,10], P2=[2,7,15], P3=[6,10,12]. K=2. Sorted by start_time. We iterate through projects, greedily selecting if slots are available or replacing a lower-profit active project if full.

  • P1 (1,5,10): Select. Current active: {P1}. Total profit: 10.
  • P2 (2,7,15): P1 is active. One slot free. Select. Current active: {P1, P2}. Total profit: 10+15=25.
  • P3 (6,10,12): P1 ends at 5. P2 is active. One slot free. Select. Current active: {P2, P3}. Total profit: 25+12=37. Maximum profit achieved is 37.
2

Example 2

Input:

projects = [[1,4,20], [2,5,10], [3,6,30], [4,7,40]], K = 2

Output:

90

Note:

Projects: P1=[1,4,20], P2=[2,5,10], P3=[3,6,30], P4=[4,7,40]. K=2. Sorted by start_time.

  • P1 (1,4,20): Select. Active: {P1}. Profit: 20.
  • P2 (2,5,10): P1 active. One slot free. Select. Active: {P1, P2}. Profit: 20+10=30.
  • P3 (3,6,30): P1, P2 active. K=2. P3's profit (30) > P2's profit (10). Replace P2 with P3. Active: {P1, P3}. Profit: 30-10+30=50.
  • P4 (4,7,40): P1 ends at 4. P3 active. One slot free. Select P4. Active: {P3, P4}. Profit: 50+40=90. Maximum profit achieved is 90.
3

Example 3

Input:

projects = [[1,3,10], [1,2,5], [2,4,12]], K = 1

Output:

12

Note:

Projects: P1=[1,3,10], P2=[1,2,5], P3=[2,4,12]. K=1. Sorted by start_time (P2, P1, P3 to handle ties consistently).

  • P2 (1,2,5): Select. Active: {P2}. Profit: 5.
  • P1 (1,3,10): P2 active. K=1. P1's profit (10) > P2's profit (5). Replace P2 with P1. Active: {P1}. Profit: 5-5+10=10.
  • P3 (2,4,12): P1 active. K=1. P3's profit (12) > P1's profit (10). Replace P1 with P3. Active: {P3}. Profit: 10-10+12=12. Maximum profit achieved is 12.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5 (number of projects)
  • 1 <= K <= N (maximum concurrent projects)
  • 1 <= start_time < end_time <= 10^9
  • 1 <= profit <= 10^9
  • The total profit can exceed the capacity of a 32-bit integer, so use a 64-bit integer type (e.g., number in TypeScript/JavaScript) for sums.

Out of scope (optional)

  • Error handling for invalid input (e.g., negative profits, start_time >= end_time). Assume valid inputs as per constraints.

What interviewers evaluate

  • Correctness: Does the solution produce the accurate maximum profit for all valid test cases?
  • Algorithm Design: Is the chosen greedy strategy sound and justified? Does it correctly handle the concurrency constraint and profit maximization?
  • Data Structure Usage: Is the use of priority queues or other data structures efficient and appropriate for the problem's constraints?
  • Time and Space Complexity: Is the solution optimized for O(N log N) time complexity and O(N) space complexity?
  • Code Quality: Is the code clean, readable, and well-structured?

Loading editor...