Abstract / Summary

A list of jobs with start and end times must be run on one cpu without overlap; find the least time to finish all jobs.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 48% (300k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation defines a generator-based solution for ordering a set of tasks on a single CPU. Each task is described by a start time and a processing duration. The algorithm maintains two priority queues: one for tasks that have not yet become available (incoming) and another for tasks that are ready to run (waiting). By repeatedly moving tasks from incoming to waiting as the simulated clock advances, the code produces the execution order that respects the earliest-available-task rule and, when durations tie, the smallest original index.

Key Steps

Building the initial heap of incoming tasks

All tasks are inserted into a min-heap keyed by their start time, duration, and original index. This preparation enables constant-time access to the next task that will become available.

incoming = []
for i, (start, duration) in enumerate(tasks):
    heappush(incoming, (start, duration, i))

Advancing the clock when the CPU is idle

If there are no ready tasks (waiting is empty), the algorithm extracts the earliest-starting task from incoming. The simulated timestamp is moved forward to the start time of that task, ensuring that idle periods are skipped efficiently.

if not waiting:
    start, duration, i = heappop(incoming)
    timestamp = max(timestamp, start)   # skip forward
    heappush(waiting, (duration, i))

Moving newly available tasks to the waiting heap

After the timestamp is set, any tasks whose start time is less than or equal to the current timestamp are transferred from incoming to waiting. Because waiting is ordered by duration (and then index), the next pop yields the optimal task to execute.

while incoming and incoming[0][0] <= timestamp:
    start, duration, i = heappop(incoming)
    heappush(waiting, (duration, i))

Executing the selected task

The task with the smallest duration (and smallest index on ties) is removed from waiting. The timestamp is incremented by the task’s duration, the count of completed tasks is updated, and the task’s original index is yielded to the caller.

duration, i = heappop(waiting)
timestamp += duration
done += 1
yield i

Loop termination

The outer while loop continues until the number of completed tasks equals the total number of tasks, guaranteeing that every task is eventually processed.

while done < len(tasks):
    ...

Edge Cases Handled

When the input list of tasks is empty, the while done < len(tasks) condition is false from the start, so the generator produces no output without raising an exception.

If multiple tasks share the same start time, they are all inserted into incoming during the initial heap construction. When the timestamp reaches that start time, the inner while loop moves every such task into waiting before any execution occurs, preserving the rule that all simultaneously available tasks are considered together.

When several ready tasks have identical durations, the secondary key in the waiting heap (i, the original index) ensures a deterministic order based on the tasks’ original positions.

If the CPU becomes idle because no tasks are ready, the algorithm correctly jumps forward to the start time of the next pending task, avoiding unnecessary iteration over idle timestamps.

Performance Optimizations

The dual-heap design eliminates the need for linear scans of the task list. Inserting all tasks into the incoming heap costs O(n log n) once, after which each task is moved at most once between the two heaps. The use of heappush and heappop provides logarithmic time for each insertion and removal, keeping the overall runtime proportional to the number of tasks times a logarithmic factor.

Skipping idle periods by setting timestamp = max(timestamp, start) prevents the algorithm from stepping through each unit of time, which would be costly for large gaps between task start times.

Yielding indices directly from the generator avoids constructing an intermediate list of results, reducing memory overhead and allowing the caller to consume the order lazily.

The comparison tuple (duration, i) in the waiting heap guarantees that the heap ordering respects both the primary duration criterion and the secondary index tie-breaker without additional conditional logic, streamlining the selection of the next task.

Imagine a busy robot worker that has a pile of chores to finish. Each chore has a time when it shows up and a length indicating how long it takes to complete.

First, the robot keeps all the tasks in a big box. It looks at the box and picks out the chores that have already arrived based on the current time. If the robot is finished with everything it was doing and is just waiting, it will jump to the time when the next chore arrives.

The robot puts all the chores that are ready to go into a special tray. It always picks the chore that takes the shortest amount of time to finish from that tray. After finishing one chore, the robot records the time it spent and checks the big box again to see if any new chores arrived while it was busy working. It repeats this process over and over until every single chore is finished.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python			TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java			Python		Go
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem					Ruby
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007						Python
	martianoff				Scala
	suxrobGM							C#
	vthwang			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
martianoff	Scala
suxrobGM	C#
vthwang	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality