Problem Statement in English

You’re given two integer arrays deadline and profit, both of length n. Each job i has a deadline deadline[i] and a profit profit[i].

Your task is to schedule the jobs in such a way that you maximize the total profit while ensuring that no two jobs overlap in their deadlines. Each job takes exactly one unit of time to complete, and you can only work on one job at a time.

Approach

This was one deceptively hard problem.

The main idea is to perform a job as close to its deadline as possible so that we can leave room for other jobs to be performed earlier.

As we perform jobs, we’re moving backwards in time, so we need to keep track of the previous start time (pst) of the last job we performed.

Sometimes the previous start time may be after the deadline of the job we’re about to perform, in which case we need to adjust the previous start time to be the deadline of the current job minus one.

We stop accepting jobs when there is no more time left to perform any job, that is when the previous start time becomes zero.

Solution in Python


def solution(deadline: List[int], profit: List[int]) -> int:
	arr = []
	
	for d, p in zip(deadline, profit):
		arr.append((d, p))
	
	arr.sort()
	
    # previous start time
	pst = arr[-1][0]
	res = c = 0
	
	for d, p in reversed(arr):
		if not pst:
			break
		c += 1
		res += p
		pst = min(pst - 1, d - 1)
		
	return c, res

Complexity

  • Time: $O(n \log n)$
    Since we need to sort the jobs based on their deadlines.

  • Space: $O(n)$
    We use an additional array to store the jobs along with their deadlines and profits.

Mistakes I Made

I had to look this one up :(

And we are done.