Total time covered by a set of bookings
Each booking is a pair [start, end] of integers with start < end,
covering the time from start up to end. Bookings may overlap, touch or nest
inside one another, and they are not in any particular order. Return the total length of time covered by
at least one booking.
Examples
| Input | Output | Why |
|---|---|---|
bookings = [[1, 3], [2, 6], [8, 10]] | 7 | 1 to 6 is covered once the first two merge (5), plus 8 to 10 (2). |
bookings = [[1, 4], [4, 5]] | 4 | Touching bookings cover 1 to 5 without a gap. |
bookings = [[1, 10], [2, 3], [4, 5]] | 9 | The short bookings sit inside the long one and add nothing. |
Constraints
- 1 ≤ n ≤ 10⁵
- 0 ≤ start < end ≤ 10⁹
Hints
Hint 1
Adding up every booking's length double-counts the overlaps. What order would let you see each overlap the moment it happens?
Hint 2
Sort by start time. A booking that starts after everything so far has ended begins a new block; otherwise it can only extend the current one.
Hint 3
Keep the current block's start and end. On a gap, add the block's length to the total and start a new block. Add the last block at the end.
Where people lose marks
- Summing every booking's length: overlaps are counted twice.
- Setting end = e instead of end = max(end, e): a booking nested inside the block would shorten it.
- Forgetting the last block, which is never followed by a gap.
- Sorting by end time: two bookings far apart can then sit next to each other while an overlapping one comes later.
Dry run on [[6,8],[1,3],[2,5],[10,12],[11,13]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6bookings, sorted by start1–302–516–8210–12311–134block1–3total0
Sort by start time: 1–3, 2–5, 6–8, 10–12, 11–13. The first booking opens a block from 1 to 3.
-
Step 2 / 6bookings, sorted by start1–302–516–8210–12311–134block1–5total0
2–5 starts at or before 3, so it overlaps the block. It extends the block to 5.
-
Step 3 / 6bookings, sorted by start1–302–516–8210–12311–134block6–8total4
6–8 starts after the block ends at 5: a gap. Close 1–5 (length 4); the total is 4. Start a new block.
-
Step 4 / 6bookings, sorted by start1–302–516–8210–12311–134block10–12total6
10–12 starts after the block ends at 8: a gap. Close 6–8 (length 2); the total is 6. Start a new block.
-
Step 5 / 6bookings, sorted by start1–302–516–8210–12311–134block10–13total6
11–13 starts at or before 12, so it overlaps the block. It extends the block to 13.
-
Step 6 / 6bookings, sorted by start1–302–516–8210–12311–134total9
No more bookings: close the last block 10–13 (length 3). Total covered: 9.
How to think about it
Overlaps are only a problem because they hide among unrelated bookings. Sorted by start time, every booking that overlaps the current block comes straight after it, so one pass is enough:
- If the next booking starts after the current block ends, there is a gap. The block is final: add its length and start a new block at this booking.
- Otherwise it overlaps or touches, and can only push the block's end further:
end = max(end, e).
The max matters: a booking nested inside the block ends earlier than the block does, and
must not shorten it. Sorting costs O(n log n) and the sweep O(n).
This is the merge-intervals sweep. Returning the merged blocks themselves, rather than their total length, is the same loop with the blocks collected in a list.
Complexity. Time O(n log n) · Space O(n) for the sorted copy
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def covered_length(bookings):
bookings = sorted(bookings) # by start time
total = 0
start, end = bookings[0] # the current block
for s, e in bookings[1:]:
if s > end: # a gap: the block is final
total += end - start
start, end = s, e
else: # overlaps or touches: extend
end = max(end, e)
return total + end - start # the last block#include <vector>
#include <algorithm>
long long solve(std::vector<std::vector<int>> b) {
std::sort(b.begin(), b.end()); // by start, then end
long long total = 0, start = b[0][0], end = b[0][1];
for (size_t i = 1; i < b.size(); ++i) {
if (b[i][0] > end) { // a gap: the block is final
total += end - start;
start = b[i][0]; end = b[i][1];
} else {
end = std::max<long long>(end, b[i][1]); // overlaps or touches: extend
}
}
return total + end - start; // the last block
}class Solution {
public long coveredLength(int[][] bookings) {
int[][] b = bookings.clone();
java.util.Arrays.sort(b, (p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
long total = 0, start = b[0][0], end = b[0][1];
for (int i = 1; i < b.length; i++) {
if (b[i][0] > end) { // a gap: the block is final
total += end - start;
start = b[i][0]; end = b[i][1];
} else {
end = Math.max(end, b[i][1]); // overlaps or touches: extend
}
}
return total + end - start; // the last block
}
}function coveredLength(bookings) {
const b = bookings.map(x => x.slice()).sort((p, q) => p[0] - q[0] || p[1] - q[1]);
let total = 0;
let [start, end] = b[0]; // the current block
for (let i = 1; i < b.length; i++) {
const [s, e] = b[i];
if (s > end) { // a gap: the block is final
total += end - start;
start = s; end = e;
} else {
end = Math.max(end, e); // overlaps or touches: extend
}
}
return total + end - start; // the last block
}fn solve(bookings: &[[i64; 2]]) -> i64 {
let mut b = bookings.to_vec();
b.sort(); // by start, then end
let (mut start, mut end) = (b[0][0], b[0][1]);
let mut total = 0;
for &[s, e] in &b[1..] {
if s > end { // a gap: the block is final
total += end - start;
start = s;
end = e;
} else {
end = end.max(e); // overlaps or touches: extend
}
}
total + end - start // the last block
}import Data.List (sort)
-- Sort by start, then sweep: extend the current block or close it on a gap.
solve :: [[Int]] -> Int
solve bookings = sweep s0 e0 rest
where
([s0, e0] : rest) = sort bookings
sweep s e [] = e - s
sweep s e ([a, b] : more)
| a > e = (e - s) + sweep a b more
| otherwise = sweep s (max e b) moreVariants to try
- Return the merged blocks rather than their total: collect each block when it closes.
- Bookings arrive one at a time and the total must be kept up to date: a balanced tree of disjoint blocks keyed by start.
- Find the longest stretch of time covered by at least two bookings: sweep over start and end events with a counter.
Next problems
Fewest meeting rooms for a day of meetings
The number of rooms needed is the most meetings that are ever running at once. Sort the starts and the ends and walk through them together.
Open the problem → Medium18 minFewest bookings to cancel so none overlap
Keeping the most bookings means removing the fewest. Sort by end time and keep every booking that fits.
Open the problem → Hard30 minMost profit from jobs that do not overlap
Each job has a value, so ending earliest is no longer safe. Sort by end time; each job either joins the best schedule ending before it starts, or is skipped.
Open the problem →Write a solution and run it against the real test table.
Keep going
Fewest meeting rooms for a day of meetings
The number of rooms needed is the most meetings that are ever running at once. Sort the starts and the ends and walk through them together.
Open the problem → Medium18 minFewest bookings to cancel so none overlap
Keeping the most bookings means removing the fewest. Sort by end time and keep every booking that fits.
Open the problem → Hard30 minMost profit from jobs that do not overlap
Each job has a value, so ending earliest is no longer safe. Sort by end time; each job either joins the best schedule ending before it starts, or is skipped.
Open the problem → IntervalsThe pattern behind it
Sort by start to merge and count overlaps; sort by end to choose. One sorted pass replaces checking every pair.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.