LeetCode 1235 - Maximum Profit in Job Scheduling

LeetCode Problem 1235

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem gives us three arrays of equal length:

• startTime[i] represents when the i-th job starts
• endTime[i] represents when the i-th job finishes
• profit[i] represents the money earned if we complete that job

Our goal is to select a subset of jobs that do not overlap in time while maximizing the total profit.

Two jobs are considered compatible if the second one starts at or after the first one ends. This detail is extremely important because the problem explicitly allows:

• one job ending at time X
• another job starting exactly at time X

For example:

• Job A: [1, 3]
• Job B: [3, 6]

These jobs are compatible and can both be chosen.

The output is a single integer representing the maximum achievable profit.

The constraints are large:

• Up to 5 * 10^4 jobs
• Time values up to 10^9

These constraints immediately rule out many naive recursive solutions. An exponential search over all subsets would be impossibly slow. Even an O(n^2) dynamic programming solution is risky for 50,000 jobs.

The problem combines several classic ideas:

• sorting intervals
• binary search
• dynamic programming

This is a variation of the classic Weighted Interval Scheduling problem.

Several edge cases are important:

• Multiple jobs may start at the same time
• Multiple jobs may end at the same time
• A job may start exactly when another ends
• The optimal answer may skip many small jobs in favor of one large job
• The optimal answer may require combining many compatible smaller jobs
• Jobs are not initially sorted

The input guarantees:

• every job has positive duration because startTime[i] < endTime[i]
• every profit is positive
• all arrays have the same length

These guarantees simplify the implementation because we never deal with invalid intervals or negative profits.

Approaches

Brute Force Approach

A brute force solution would try every possible subset of jobs.

For each subset:

1. Check whether the selected jobs overlap
2. If valid, compute the total profit
3. Keep track of the maximum profit found

This guarantees correctness because every possible combination is examined.

However, this approach is extremely inefficient. With n jobs, there are 2^n possible subsets. Even for relatively small values of n, this becomes computationally impossible.

Another slightly improved brute force method uses recursion:

• At each job, choose either:

• take the job

• skip the job

• If taking the job, recursively search for the next compatible job

Although this avoids generating invalid subsets explicitly, the same subproblems are recomputed repeatedly, leading to exponential complexity.

Key Insight

The critical observation is that once jobs are sorted by start time or end time, the problem develops an optimal substructure.

Suppose we are currently considering job i.

We have only two meaningful choices:

1. Skip job i
2. Take job i, then continue with the next non-overlapping job

If we can quickly find the next compatible job, then the remaining problem becomes identical in structure to the original one.

This naturally leads to dynamic programming.

The remaining challenge is efficiently locating the next compatible job. Since the jobs are sorted, we can use binary search to find the first job whose start time is greater than or equal to the current job's end time.

This transforms the solution into:

• sorting
• binary search
• memoized dynamic programming

The final complexity becomes O(n log n), which is efficient enough for 50,000 jobs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively tries every subset of jobs
Optimal	O(n log n)	O(n)	Sorting + binary search + dynamic programming

Algorithm Walkthrough

1. Combine all job information into a single structure.

Each job contains:

• start time
• end time
• profit

This makes sorting and processing much easier. 2. Sort the jobs by start time.

Sorting is necessary because binary search only works on ordered data. Once jobs are sorted, all future compatible jobs appear after the current job. 3. Extract all start times into a separate array.

This array allows efficient binary searching for the next compatible job. 4. Define a dynamic programming function dfs(index).

This function returns the maximum profit obtainable starting from job index. 5. At each job, compute two choices.

First choice:

• skip the current job
• move directly to index + 1

Second choice:

• take the current job
• binary search for the next compatible job
• add the current profit plus the best future profit

6. Use binary search to find the next compatible job.

We search for the first job whose start time is greater than or equal to the current job's end time.

This works because the jobs are sorted by start time. 7. Store computed results using memoization.

Without memoization, the recursion would recompute identical states many times. Caching ensures each state is solved once. 8. Return the best choice.

The answer for each state is:

max(skip_current, take_current) 9. Start the recursion from index 0.

This computes the best possible profit across all jobs.

Why it works

For every job, the algorithm considers all valid possibilities through two exhaustive choices:

• either include the current job
• or exclude it

If the current job is included, binary search guarantees that we jump directly to the next compatible job, ensuring no overlaps occur.

Dynamic programming guarantees optimality because each subproblem stores the maximum achievable profit from a given index onward. Since every future decision depends only on the remaining jobs, the problem has optimal substructure.

Memoization ensures each subproblem is solved exactly once.

Python Solution

from typing import List
from bisect import bisect_left
from functools import lru_cache

class Solution:
    def jobScheduling(
        self,
        startTime: List[int],
        endTime: List[int],
        profit: List[int]
    ) -> int:

        jobs = sorted(zip(startTime, endTime, profit))

        starts = [job[0] for job in jobs]

        @lru_cache(None)
        def dfs(index: int) -> int:
            if index >= len(jobs):
                return 0

            # Option 1: skip current job
            skip_profit = dfs(index + 1)

            current_start, current_end, current_profit = jobs[index]

            # Find next compatible job
            next_index = bisect_left(starts, current_end)

            # Option 2: take current job
            take_profit = current_profit + dfs(next_index)

            return max(skip_profit, take_profit)

        return dfs(0)

The implementation begins by combining the three input arrays into a list of tuples. Each tuple represents one job containing:

• start time
• end time
• profit

The jobs are sorted by start time because binary search requires ordered data.

The starts array stores only the start times. This is important because Python's bisect_left operates directly on sorted arrays.

The recursive dfs(index) function computes the best possible profit starting from a particular job index.

The base case occurs when the index moves beyond the final job. In that situation, no more profit can be earned, so the function returns 0.

Inside the recursion, the algorithm evaluates two possibilities:

• skip the current job
• take the current job

When taking the current job, binary search identifies the first compatible future job. The current profit is then added to the optimal future profit returned by recursion.

The lru_cache decorator memoizes results so each state is computed once.

Finally, dfs(0) returns the optimal answer starting from the first job.

Go Solution

package main

import (
	"sort"
)

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	type Job struct {
		start  int
		end    int
		profit int
	}

	n := len(startTime)

	jobs := make([]Job, n)

	for i := 0; i < n; i++ {
		jobs[i] = Job{
			start:  startTime[i],
			end:    endTime[i],
			profit: profit[i],
		}
	}

	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i].start < jobs[j].start
	})

	starts := make([]int, n)

	for i := 0; i < n; i++ {
		starts[i] = jobs[i].start
	}

	dp := make([]int, n)

	var dfs func(int) int

	dfs = func(index int) int {
		if index >= n {
			return 0
		}

		if dp[index] != 0 {
			return dp[index]
		}

		// Option 1: skip current job
		skipProfit := dfs(index + 1)

		currentJob := jobs[index]

		// Find next compatible job
		nextIndex := sort.Search(
			n,
			func(i int) bool {
				return starts[i] >= currentJob.end
			},
		)

		// Option 2: take current job
		takeProfit := currentJob.profit + dfs(nextIndex)

		if skipProfit > takeProfit {
			dp[index] = skipProfit
		} else {
			dp[index] = takeProfit
		}

		return dp[index]
	}

	return dfs(0)
}

The Go implementation follows the same algorithmic structure as the Python version.

A custom Job struct stores job information cleanly.

Go does not provide built in memoization decorators like Python's lru_cache, so we use a dp slice manually. Since profits are always positive, a value of 0 safely indicates an uncomputed state.

Binary search is implemented using sort.Search, which efficiently finds the first compatible job index.

Go slices are used instead of arrays because their size is dynamic and more convenient for algorithmic problems.

Integer overflow is not a concern here because the maximum total profit fits comfortably inside Go's int range on modern systems.

Worked Examples

Example 1

Input:

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

After sorting:

Index	Start	End	Profit
0	1	3	50
1	2	4	10
2	3	5	40
3	3	6	70

Start times array:

[1, 2, 3, 3]

Now evaluate recursively from the back.

State: dfs(3)

Current job:

[3, 6, 70]

Binary search for start >= 6:

nextIndex = 4

Choices:

Choice	Profit
Skip	0
Take	70 + 0 = 70

Result:

dfs(3) = 70

State: dfs(2)

Current job:

[3, 5, 40]

Binary search for start >= 5:

nextIndex = 4

Choices:

Choice	Profit
Skip	70
Take	40

Result:

dfs(2) = 70

State: dfs(1)

Current job:

[2, 4, 10]

Binary search for start >= 4:

nextIndex = 4

Choices:

Choice	Profit
Skip	70
Take	10

Result:

dfs(1) = 70

State: dfs(0)

Current job:

[1, 3, 50]

Binary search for start >= 3:

nextIndex = 2

Choices:

Choice	Profit
Skip	70
Take	50 + 70 = 120

Final result:

120

Example 2

Input:

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

Sorted jobs:

Index	Start	End	Profit
0	1	3	20
1	2	5	20
2	3	10	100
3	4	6	70
4	6	9	60

Key decisions:

• Taking job 2 yields 100
• Taking jobs 0, 3, and 4 yields 20 + 70 + 60 = 150

The algorithm correctly chooses the larger total:

150

Example 3

Input:

startTime = [1,1,1]
endTime   = [2,3,4]
profit    = [5,6,4]

All jobs overlap because they all start at time 1.

Therefore, only one job may be selected.

Profits:

Job	Profit
[1,2]	5
[1,3]	6
[1,4]	4

Maximum:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting plus one binary search per job
Space	O(n)	Memoization cache and auxiliary arrays

The sorting step costs O(n log n).

Each dynamic programming state is computed once because of memoization. For every state, we perform a binary search costing O(log n).

Since there are n states, the total DP cost is:

O(n log n)

The memoization cache, recursion stack, and auxiliary arrays together require linear space.

Test Cases

from typing import List

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        from bisect import bisect_left
        from functools import lru_cache

        jobs = sorted(zip(startTime, endTime, profit))
        starts = [job[0] for job in jobs]

        @lru_cache(None)
        def dfs(i):
            if i >= len(jobs):
                return 0

            skip = dfs(i + 1)

            next_i = bisect_left(starts, jobs[i][1])

            take = jobs[i][2] + dfs(next_i)

            return max(skip, take)

        return dfs(0)

solution = Solution()

# Example 1
assert solution.jobScheduling(
    [1,2,3,3],
    [3,4,5,6],
    [50,10,40,70]
) == 120  # choose jobs [1,3] and [3,6]

# Example 2
assert solution.jobScheduling(
    [1,2,3,4,6],
    [3,5,10,6,9],
    [20,20,100,70,60]
) == 150  # choose multiple compatible jobs

# Example 3
assert solution.jobScheduling(
    [1,1,1],
    [2,3,4],
    [5,6,4]
) == 6  # all jobs overlap

# Single job
assert solution.jobScheduling(
    [1],
    [2],
    [100]
) == 100  # smallest valid input

# Jobs that chain perfectly
assert solution.jobScheduling(
    [1,2,3],
    [2,3,4],
    [10,20,30]
) == 60  # all jobs compatible

# Large profit single job vs many small jobs
assert solution.jobScheduling(
    [1,2,3],
    [4,5,6],
    [100,20,20]
) == 100  # single large job better

# Multiple overlapping jobs
assert solution.jobScheduling(
    [1,1,1,1],
    [2,3,4,5],
    [5,6,7,8]
) == 8  # choose highest profit only

# Compatible jobs with equal boundaries
assert solution.jobScheduling(
    [1,3,6],
    [3,6,9],
    [20,30,40]
) == 90  # endpoints allowed to touch

# Unsorted input
assert solution.jobScheduling(
    [4,1,2],
    [6,3,5],
    [70,20,20]
) == 90  # algorithm must sort internally

# Many small compatible jobs beat one large job
assert solution.jobScheduling(
    [1,2,3,4],
    [2,3,4,5],
    [25,25,25,25]
) == 100  # combine all compatible jobs

Test	Why
Example 1	Validates basic compatibility handling
Example 2	Verifies optimal combination selection
Example 3	Ensures overlapping jobs are rejected correctly
Single job	Smallest valid input
Perfect chain	Confirms jobs can connect at equal endpoints
Large single profit	Ensures algorithm compares global profit correctly
All overlapping	Tests choosing only the best job
Equal boundaries	Validates inclusive endpoint rule
Unsorted input	Ensures sorting logic works
Many compatible jobs	Confirms cumulative profit optimization

Edge Cases

One important edge case occurs when jobs touch exactly at endpoints. Many interval scheduling implementations mistakenly treat these as overlapping. In this problem, a job ending at time X is compatible with another starting at time X. The implementation handles this correctly by using bisect_left(starts, current_end), which searches for the first start time greater than or equal to the current end time.

Another important edge case is when all jobs overlap. In such situations, the algorithm must select exactly one job, specifically the one with the maximum profit. The recursive dynamic programming approach naturally handles this because every state compares taking the current job versus skipping it.

A third important edge case is unsorted input. The problem does not guarantee any ordering of jobs. A naive solution that assumes sorted data would fail binary searches and compatibility checks. The implementation explicitly sorts all jobs before processing, ensuring correctness regardless of input order.

A fourth subtle edge case involves multiple jobs sharing the same start time. Binary search and dynamic programming still function correctly because the jobs remain properly ordered after sorting. The recursion explores all possibilities and memoization prevents redundant computation.

Finally, very large time values up to 10^9 can cause problems in algorithms that attempt timeline simulation or dense arrays indexed by time. This solution avoids that issue entirely because it operates only on sorted job indices and binary search, never on actual time ranges.