Resurfaced Road Stretches
A county resurfaced a long country road this summer. Several crews worked on it, and each crew logged the stretch it covered as a pair of kilometre markers, like [3, 6] for kilometres 3 to 6. Crews often overlapped, and the log is in no particular order.
The county wants a clean map for drivers: the fewest stretches that show exactly which parts of the road are new.
Your task
Write mergeStretches(jobs). Each job is [start, end] with start ≤ end. Return the combined stretches as a list of [start, end] pairs, sorted by start, where no two stretches overlap or touch.
Two jobs belong to the same stretch if they share any point, including just an endpoint: [2, 5] and [5, 9] become [2, 9]. An empty log returns an empty list.
mergeStretches(jobs: int[][]) → int[][]
Examples
jobs = [[8, 10], [1, 4], [3, 6]]
[[1, 6], [8, 10]]
Sorted by start the jobs are [1, 4], [3, 6], [8, 10]. The first two share kilometres 3 to 4, so together they cover 1 to 6. The job at 8 starts after 6, so there is a gap of old road between them.
jobs = [[2, 5], [5, 9], [12, 14]]
[[2, 9], [12, 14]]
One crew stopped at kilometre 5 and another started at 5, so there is no gap: 2 to 9 is one continuous new stretch.
Constraints
- 0 ≤ jobs.length ≤ 10,000
- 0 ≤ start ≤ end ≤ 1,000,000,000
Start with brute force
Keep scanning all pairs of stretches; whenever two overlap, replace them with their union, and start over. Stop when no pair overlaps, then sort.
Each scan checks O(n²) pairs, and you may need up to n scans, so it is O(n³) in the worst case. With 10,000 jobs that is around a trillion comparisons. The waste is checking pairs that are far apart on the road.
Hints
0 of 4 shown- Hint 1
Look at the first example in the order it was logged: [8, 10] comes first, but it is the last stretch on the road. What would make it easier to see which jobs touch?
- Hint 2
Sort the jobs by their start. Now, can a job overlap a stretch you finished long ago, or only the most recent one?
- Hint 3
After sorting, keep a current stretch. The next job either starts at or before the current stretch's end (so it joins it) or starts after it (so a new stretch begins).
- Hint 4
Sort by start. Put the first job in the result. For each next job: if its start ≤ the end of the last stretch in the result, set that end to the larger of the two ends. Otherwise append the job as a new stretch. Watch the "larger of the two ends": a short job inside a long one must not shrink it.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Once the jobs are sorted by start, a job can only overlap the stretch you are building right now. Every earlier stretch ended before the current one began, and this job starts even later. So one pass is enough.
Trace the first example. Sorted: [1, 4], [3, 6], [8, 10].
[1, 4]: the result is empty, so start a stretch. Result:[[1, 4]].[3, 6]: 3 ≤ 4, so it joins. The end becomes max(4, 6) = 6. Result:[[1, 6]].[8, 10]: 8 > 6, a gap. New stretch. Result:[[1, 6], [8, 10]].
Two details trip people up. Use ≤, not <, because touching stretches join. And take the max of the ends: in [1, 10], [2, 3] the second job ends earlier and must not cut the stretch short.
function mergeStretches(jobs) {
const sorted = [...jobs].sort((a, b) => a[0] - b[0]);
const result = [];
for (const [start, end] of sorted) {
const last = result[result.length - 1];
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end); // joins the current stretch
} else {
result.push([start, end]); // gap before it: new stretch
}
}
return result;
}def merge_stretches(jobs):
result = []
for start, end in sorted(jobs):
if result and start <= result[-1][1]:
result[-1][1] = max(result[-1][1], end) # joins the current stretch
else:
result.append([start, end]) # gap before it: new stretch
return resultRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.