Maximum Profit from Scheduled Deliveries — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Dynamic Programming and solve the Maximum Profit from Scheduled Deliveries problem optimally.
O(N log N)O(N)Problem Description
You are optimizing the schedule for a fleet of autonomous delivery drones operating in a single time-slot system. You are given an array of delivery jobs, where each job is represented by a pair [profit, deadline]. The profit is the revenue generated upon successful completion, and the deadline is the latest time unit by which the job must be finished. The drone can execute at most one job per time unit. A job is considered valid only if it is completed at or before its specified deadline. Your objective is to determine the maximum total profit achievable by selecting and scheduling a subset of these jobs such that no job misses its deadline.
The input consists of an array 'jobs' of size n, where jobs[i] = [profit_i, deadline_i]. The output should be a single integer representing the maximum possible profit. Note that the time units are discrete and start from 1. If a job has a deadline of d, it can be scheduled in any time slot t where 1 <= t <= d. You do not need to return the schedule itself, only the maximum profit value.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Profit from Scheduled Deliveries"
WHY DOES IT MATTER?
Job sequencing with deadlines is a foundational greedy‑plus‑DSU pattern that appears in scheduling, resource allocation, and deadline‑driven profit maximization problems, teaching candidates how to combine ordering heuristics with efficient slot management.
OPTIMIZATION CHALLENGE
The key insight is to avoid a linear scan for a free slot by compressing the timeline with a Union‑Find structure, turning each slot lookup into an almost O(1) operation and thus preserving the O(N log N) bound set by sorting.
REAL-WORLD CONNECTION
Think of a warehouse loading dock where trucks (jobs) arrive with different fees and must be docked before a departure deadline; assigning each truck to the latest possible dock slot frees earlier docks for other trucks, mirroring the algorithm's slot‑selection logic.
During an interview, first sort by profit, then implement a DSU with path compression; remember to union the occupied slot with its predecessor, and always query find(deadline) to get the best available slot.
COMPLEXITY AT A GLANCE
O(N log N)O(N)Core Theory — Why This Approach?
The problem is a classic instance of the Job Sequencing with Deadlines problem, which can be modeled as a weighted interval scheduling task where each job occupies exactly one unit of time. A naive exhaustive search would try every permutation of jobs, leading to O(N!) time, which is infeasible for N > 20. The optimal paradigm leverages a greedy strategy: sort jobs by descending profit and then assign each job to the latest available time slot before its deadline. This works because placing a high‑profit job as late as possible leaves earlier slots free for other jobs, guaranteeing maximal total profit. To efficiently locate the latest free slot we use a Disjoint Set Union (DSU) / Union‑Find structure that supports "find" of the greatest free time ≤ deadline in near‑constant amortized time, turning the overall algorithm into O(N log N) due to the initial sort.
The DSU maintains a parent array where each time slot points to the next earlier free slot after it gets occupied. When a job is placed at slot t, we union t with t‑1, effectively marking t as unavailable and redirecting future finds to the next candidate. This clever compression of the search space eliminates the O(N) scan that a simple boolean array would require, reducing the time complexity dramatically while keeping space linear. The approach exemplifies how greedy ordering combined with a suitable data structure yields an optimal solution for a combinatorial optimization problem.
Interview Questions on This Problem
Q1How would you modify the algorithm if each job could take multiple time units instead of exactly one?
Sort jobs by profit per unit time, then use a priority queue to schedule jobs in earliest‑available slots, checking feasibility with a segment tree or binary indexed tree to find a contiguous block of free slots of the required length.
Q2Explain why sorting by profit alone (without the DSU slot‑finding step) does not guarantee an optimal solution.
Profit sorting determines the order of consideration, but without placing each job in the latest possible free slot, earlier high‑profit jobs may occupy slots needed by later jobs with tighter deadlines, causing sub‑optimal total profit.
Q3Can the job sequencing problem be solved using dynamic programming? If so, outline the DP state and transition.
Yes, define DP[i][t] as the maximum profit using the first i jobs within t time units; transition is DP[i][t] = max(DP[i‑1][t], profit_i + DP[i‑1][t‑1]) if deadline_i ≥ t, otherwise DP[i][t] = DP[i‑1][t]. This yields O(N^2) time, which is slower than the greedy‑DSU solution.
Examples
Input
jobs = [[50, 2], [10, 1], [70, 3], [30, 1]]
Output
150
Explanation: We have 4 jobs. Job 1: profit 50, deadline 2. Job 2: profit 10, deadline 1. Job 3: profit 70, deadline 3. Job 4: profit 30, deadline 1. To maximize profit, we should prioritize high-profit jobs with feasible deadlines. We can schedule Job 4 (profit 30) at time 1. We can schedule Job 1 (profit 50) at time 2. We can schedule Job 3 (profit 70) at time 3. Job 2 (profit 10) cannot be scheduled because time 1 is occupied by Job 4, and its deadline is 1. Total profit = 30 + 50 + 70 = 150.
Input
jobs = [[100, 1], [200, 2], [300, 3]]
Output
600
Explanation: Job 1: profit 100, deadline 1. Job 2: profit 200, deadline 2. Job 3: profit 300, deadline 3. We can schedule Job 1 at time 1, Job 2 at time 2, and Job 3 at time 3. All jobs meet their deadlines. Total profit = 100 + 200 + 300 = 600.
Input
jobs = [[10, 1], [20, 1], [30, 1]]
Output
30
Explanation: All three jobs have a deadline of 1. Only one job can be executed in time slot 1. We must choose the job with the highest profit. Job 3 has the highest profit (30). Therefore, the maximum profit is 30.
Input
jobs = [[5, 5], [4, 4], [3, 3], [2, 2], [1, 1]]
Output
15
Explanation: Job 1: profit 5, deadline 5. Job 2: profit 4, deadline 4. Job 3: profit 3, deadline 3. Job 4: profit 2, deadline 2. Job 5: profit 1, deadline 1. We can schedule Job 5 at time 1, Job 4 at time 2, Job 3 at time 3, Job 2 at time 4, and Job 1 at time 5. All jobs are scheduled within their deadlines. Total profit = 1 + 2 + 3 + 4 + 5 = 15.
Constraints
- 1 <= jobs.length <= 10^4
- 1 <= jobs[i][0] <= 10^4
- 1 <= jobs[i][1] <= 10^4
- The sum of deadlines across all jobs is at most 10^5
Optimal Approach & Strategy
Sort jobs by profit, then assign each to the latest available slot before its deadline using a Union‑Find to locate free slots in near‑constant time.
Brute Force Approach
Try every permutation of jobs and compute the profit of each feasible schedule, keeping the maximum.
Code Solutions
// Function to calculate maximum profit from scheduled deliveries
function maxProfit(jobs) {
// Sort jobs by profit in descending order
jobs.sort((a, b) => b[0] - a[0]);
const maxDeadline = Math.max(...jobs.map(j => j[1]));
const slot = new Array(maxDeadline + 1).fill(-1);
let totalProfit = 0;
for (let i = 0; i < jobs.length; i++) {
for (let d = jobs[i][1]; d > 0; d--) {
if (slot[d] === -1) {
slot[d] = i;
totalProfit += jobs[i][0];
break;
}
}
}
return totalProfit;
}
// Example usage:
const jobs = [[50,2],[10,1],[70,3],[30,1]];
console.log(maxProfit(jobs)); // 150#include <bits/stdc++.h>
using namespace std;
int maxProfit(vector<pair<int,int>>& jobs) {
// Sort jobs by profit in descending order
sort(jobs.begin(), jobs.end(), [](const auto& a, const auto& b){return a.first > b.first;});
int n = jobs.size();
// Find maximum deadline to determine number of slots
int maxDeadline = 0;
for (auto &job : jobs) maxDeadline = max(maxDeadline, job.second);
vector<int> slot(maxDeadline + 1, -1); // slot[i] holds index of job scheduled at time i
int totalProfit = 0;
for (int i = 0; i < n; ++i) {
// Find a free slot for this job (starting from its deadline)
for (int d = jobs[i].second; d > 0; --d) {
if (slot[d] == -1) {
slot[d] = i;
totalProfit += jobs[i].first;
break;
}
}
}
return totalProfit;
}
int main() {
vector<pair<int,int>> jobs = {{50,2},{10,1},{70,3},{30,1}};
cout << maxProfit(jobs) << endl; // Output: 150
return 0;
}public class Solution {
// Function to calculate maximum profit from scheduled deliveries
public int maxProfit(int[][] jobs) {
// Sort jobs by profit in descending order
java.util.Arrays.sort(jobs, (a, b) -> Integer.compare(b[0], a[0]));
int maxDeadline = 0;
for (int[] job : jobs) {
if (job[1] > maxDeadline) maxDeadline = job[1];
}
int[] slot = new int[maxDeadline + 1];
java.util.Arrays.fill(slot, -1);
int totalProfit = 0;
for (int i = 0; i < jobs.length; i++) {
for (int d = jobs[i][1]; d > 0; d--) {
if (slot[d] == -1) {
slot[d] = i;
totalProfit += jobs[i][0];
break;
}
}
}
return totalProfit;
}
public static void main(String[] args) {
int[][] jobs = {{50,2},{10,1},{70,3},{30,1}};
Solution sol = new Solution();
System.out.println(sol.maxProfit(jobs)); // 150
}
}def max_profit(jobs):
"""Return maximum profit from scheduled deliveries.
jobs: List of [profit, deadline]"""
# Sort jobs by profit descending
jobs.sort(key=lambda x: -x[0])
max_deadline = max(d for _, d in jobs)
slot = [-1] * (max_deadline + 1)
total = 0
for i, (profit, deadline) in enumerate(jobs):
for d in range(deadline, 0, -1):
if slot[d] == -1:
slot[d] = i
total += profit
break
return total
# Example usage
jobs = [[50,2],[10,1],[70,3],[30,1]]
print(max_profit(jobs)) # 150// Function to calculate maximum profit from scheduled deliveries
function maxProfit(jobs) {
// Sort jobs by profit in descending order
jobs.sort((a, b) => b[0] - a[0]);
const maxDeadline = Math.max(...jobs.map(j => j[1]));
const slot = new Array(maxDeadline + 1).fill(-1);
let totalProfit = 0;
for (let i = 0; i < jobs.length; i++) {
for (let d = jobs[i][1]; d > 0; d--) {
if (slot[d] === -1) {
slot[d] = i;
totalProfit += jobs[i][0];
break;
}
}
}
return totalProfit;
}
// Example usage:
const jobs = [[50,2],[10,1],[70,3],[30,1]];
console.log(maxProfit(jobs)); // 150Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.