Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
The platform saves a backup of its metadata at chosen times, called checkpoints. A job is covered if at least one checkpoint happens while that job is running. Every checkpoint pauses writes for a moment, so the team wants as few as possible, while still covering every job.
Write fewest_checkpoints(jobs). It takes jobs, a list of [start, end] lists, in minutes, as closed ranges. It returns a dict {"count": int, "times": list[int]}: the smallest number of checkpoint times and the times themselves, in ascending order.
Function to write
fewest_checkpoints(jobs: list[list[int]]) -> dictA dict with the smallest number of checkpoints and their times in ascending order.
How to approach it
Sort by when jobs END, not when they start. The job that ends first has to be covered, and the best place for its checkpoint is exactly its end.
Sample cases
+ 3 held back until you submit
a few overlapping jobs
A checkpoint at 6 covers the first two jobs and a checkpoint at 12 covers the last two: 2 checkpoints.
Input
Argument 1
[
[
1,
6
],
[
2,
8
],
[
7,
12
],
[
10,
16
]
]Returns
{
'count': 2,
'times': [
6,
12
]
}a long job hiding short ones
Placing points at job starts spends four checkpoints (0, 10, 30, 50) where three suffice. By end time: 20, 40, 60.
Input
Argument 1
[
[
0,
100
],
[
10,
20
],
[
30,
40
],
[
50,
60
]
]Returns
{
'count': 3,
'times': [
20,
40,
60
]
}jobs that share an endpoint
Closed ranges: a checkpoint at 5 is inside both [1, 5] and [5, 9], so 2 checkpoints cover all three.
Input
Argument 1
[
[
1,
5
],
[
5,
9
],
[
9,
12
]
]Returns
{
'count': 2,
'times': [
5,
12
]
}no jobs
Nothing needs covering, so zero checkpoints and an empty list of times.
Input
Argument 1
[] (empty list)
Returns
{
'count': 0,
'times': []
}Constraints
[1, 5] and [5, 9].count is the smallest possible number of checkpoints, and times has exactly that many entries in ascending order.end < start can never be covered. Ignore it.{"count": 0, "times": []}.Worked example
Take the jobs [1, 6], [2, 8], [7, 12] and [10, 16]. Sort by end: 6, 8, 12, 16. The first job ends at 6, so put a checkpoint at 6. It is inside [2, 8] too (2 is at most 6), so that job is covered. [7, 12] starts at 7, after 6, so it is not covered: put a checkpoint at 12. [10, 16] starts at 10, at most 12, so it is covered. The answer is {"count": 2, "times": [6, 12]}.
The trap: on [[0, 3], [1, 2], [2, 10]], a plan that places points at job starts chooses 0 first and then needs more. Ending at the earliest end, 2, covers all three jobs.
What this tests
A greedy interval choice, LeetCode 'Minimum Number of Arrows to Burst Balloons'. The skill is knowing which sort key makes the greedy step safe. Sorting by end works for a reason. The earliest-ending job must be covered by some point at or before its end. Pushing that point as late as allowed (its end) can only help later jobs. Data engineers meet this when choosing the fewest snapshots, scans or maintenance pauses.
fewest_checkpoints(jobs: list[list[int]]) -> dictSubmit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.