Maximum Profit in Job Scheduling - Practice Coding Problems

Maximum Profit in Job Scheduling - Problem

Job Scheduling for Maximum Profit

Imagine you're a freelance consultant with multiple job offers, but you can't work on overlapping projects. You have n jobs available, where each job i has:

• Start time: startTime[i]
• End time: endTime[i]
• Profit: profit[i]

Your goal is to maximize your total earnings by selecting a subset of non-overlapping jobs. Note that if a job ends at time X, you can immediately start another job that begins at time X.

Example: Jobs [(1,3,$20), (2,5,$30), (4,6,$70)] → Choose jobs 1 and 3 for profit $90

Input & Output

example_1.py — Basic Case

$ Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

› Output: 120

💡 Note: Select jobs 1 (1-3, profit 50) and job 4 (3-6, profit 70). Total profit = 50 + 70 = 120. Job 3 can't be selected because it overlaps with both selected jobs.

example_2.py — No Overlaps

$ Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

› Output: 150

💡 Note: Select jobs 1 (1-3, profit 20), 4 (4-6, profit 70), and 5 (6-9, profit 60). These don't overlap: 1-3, 4-6, 6-9. Total = 20 + 70 + 60 = 150.

example_3.py — Single Job

$ Input: startTime = [1], endTime = [2], profit = [50]

› Output: 50

💡 Note: Only one job available, so select it for profit 50.

Constraints

1 ≤ startTime.length == endTime.length == profit.length ≤ 5 * 10⁴
1 ≤ startTime[i] < endTime[i] ≤ 10⁹
1 ≤ profit[i] ≤ 10⁴
Jobs can start immediately when another ends (endTime[i] == startTime[j] is valid)

Visualization

Tap to expand

Understanding the Visualization

Timeline Setup

Arrange all potential concerts on a timeline, showing their duration and profit

Smart Selection

Use binary search to quickly find which previous concerts don't conflict with each new option

Profit Maximization

For each concert, decide whether to book it (plus best previous combination) or skip it

Key Takeaway

🎯 Key Insight: By sorting concerts by end time and using binary search to find compatible previous bookings, we can efficiently build the optimal schedule that maximizes venue profit while avoiding conflicts.

Asked in

G Google 42 a Amazon 38 ⊞ Microsoft 31 f Meta 25

The optimal approach uses Dynamic Programming with Binary Search achieving O(n log n) time complexity. Sort jobs by end time, then for each job use binary search to efficiently find the latest non-conflicting previous job, building up the maximum profit incrementally with the recurrence: dp[i] = max(dp[i-1], profit[i] + dp[prev_compatible]).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Try All Combinations)	O(n * 2^n)	O(1)	Generate all possible job combinations and find the maximum profit among valid ones
Dynamic Programming + Binary Search (Optimal)	O(n log n)	O(n)	Sort jobs by end time, use DP with binary search to find optimal non-conflicting combinations

Brute Force (Try All Combinations) — Algorithm Steps

Generate all possible subsets of jobs using bit manipulation
For each subset, check if all jobs are non-overlapping
Calculate total profit for valid subsets
Return the maximum profit found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^n possible combinations using bit masks

Check Overlaps

For each subset, verify no jobs have overlapping time ranges

Calculate Profit

Sum profits for valid combinations and track maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start, end, profit;
} Job;

int compare(const void *a, const void *b) {
    return ((Job*)a)->start - ((Job*)b)->start;
}

int jobScheduling(int* startTime, int startTimeSize, int* endTime, int endTimeSize, int* profit, int profitSize) {
    int n = startTimeSize;
    Job* jobs = (Job*)malloc(n * sizeof(Job));
    for (int i = 0; i < n; i++) {
        jobs[i] = (Job){startTime[i], endTime[i], profit[i]};
    }
    
    int maxProfit = 0;
    
    // Try all 2^n possible subsets
    for (int mask = 0; mask < (1 << n); mask++) {
        Job* currentJobs = (Job*)malloc(n * sizeof(Job));
        int currentSize = 0;
        int currentProfit = 0;
        
        // Build current subset
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                currentJobs[currentSize++] = jobs[i];
                currentProfit += jobs[i].profit;
            }
        }
        
        // Check if jobs overlap
        int valid = 1;
        qsort(currentJobs, currentSize, sizeof(Job), compare);
        for (int i = 1; i < currentSize; i++) {
            if (currentJobs[i-1].end > currentJobs[i].start) {
                valid = 0;
                break;
            }
        }
        
        if (valid && currentProfit > maxProfit) {
            maxProfit = currentProfit;
        }
        
        free(currentJobs);
    }
    
    free(jobs);
    return maxProfit;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * 2^n)

2^n subsets to check, each requiring O(n) time to validate overlaps

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

73.9K Views

High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Try All Combinations) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler