Daily DSA: Project Deadline Management (Medium)
Problem Statement
You are a project manager with $N$ potential projects. Each project $i$ is characterized by two integers: a deadline $d_i$ and a profit $p_i$.
- Each project takes exactly 1 unit of time to complete.
- For a project to yield profit, it must be completed by its deadline. Specifically, if a project has a deadline $d_i$, it must be finished at or before time $d_i$.
- Time starts at $T = 0$. This means a project with deadline $d=1$ can be completed in the time slot $[0, 1)$. A project with deadline $d=2$ can be completed in either $[0, 1)$ or $[1, 2)$.
Your goal is to determine the maximum total profit you can achieve by strategically choosing which projects to complete and in what order.
Examples
Example 1:
Input: projects = [[2, 50], [1, 20], [2, 100], [1, 30]]
Output: 150
Explanation:
- We can perform the project with profit 30 in the slot [0, 1) and the project with profit 100 in the slot [1, 2). Total = 130.
- Alternatively, we can perform the project with profit 50 in the slot [0, 1) and the project with profit 100 in the slot [1, 2). Total = 150. This is the maximum.
Example 2:
Input: projects = [[1, 10], [1, 20], [1, 30]]
Output: 30
Explanation: All projects have a deadline of 1. You can only complete one project before time $T=1$. You choose the one with the highest profit.
Constraints
- $1 \le N \le 10^5$
- $1 \le d_i \le 10^9$
- $1 \le p_i \le 10^9$
Approach
Since each project takes 1 unit of time and we want to maximize profit, a greedy approach combined with a priority queue is optimal.
- Sort Projects: First, sort all projects based on their deadlines in ascending order. This allows us to process projects as their time constraints become relevant.
- Tentative Selection: Use a min-priority queue (min-heap) to store the profits of the projects we have currently decided to undertake.
- Iterate and Adjust: For each project $(d_i, p_i)$:
- If the number of projects currently in our min-heap is less than the current project’s deadline $d_i$, we have enough time to add this project to our schedule. Push $p_i$ into the heap.
- If the number of projects in our heap is equal to $d_i$, we cannot simply add another project because we’ve already filled $d_i$ slots. However, we can replace one of our previously selected projects if the current project’s profit $p_i$ is higher than the minimum profit in our heap. If $p_i > heap.top()$, we remove the minimum profit and add $p_i$.
- Final Result: The sum of all profits remaining in the min-heap is our maximum total profit.
C++ Solution
#include <vector>
#include <algorithm>
#include <queue>
class Solution {
public:
long long maxProfit(std::vector<std::vector<int>>& projects) {
// Sort projects by deadline
std::sort(projects.begin(), projects.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return a[0] < b[0];
});
// Min-heap to keep track of the profits of selected projects
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
for (const auto& project : projects) {
int deadline = project[0];
int profit = project[1];
if (pq.size() < (size_t)deadline) {
// We have a free slot before or at this deadline
pq.push(profit);
} else if (!pq.empty() && profit > pq.top()) {
// Swap the least profitable project with the current one
pq.pop();
pq.push(profit);
}
}
long long totalProfit = 0;
while (!pq.empty()) {
totalProfit += pq.top();
pq.pop();
}
return totalProfit;
}
};
Complexity Analysis
- Time Complexity: $O(N \log N)$, where $N$ is the number of projects. Sorting the projects takes $O(N \log N)$, and each of the $N$ projects is pushed/popped from the priority queue at most once, which takes $O(\log N)$ per operation.
- Space Complexity: $O(N)$ to store the projects in the priority queue in the worst case (though practically it’s limited by the maximum deadline).