Combine Overlapping Booking Ranges
Solve this ProblemA reservation system holds a list of booked time ranges in no particular order. Ranges that overlap — including ranges that merely touch at a single point — should be combined into one larger range that covers them all. Return the resulting combined ranges, sorted by start.
Repeatedly searching for overlapping pairs and merging them works but re-scans the list again and again. If the ranges are sorted by start time first, a single left-to-right sweep can build each combined range one after another.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ bookings.length ≤ 12; each booking is [start, end] with 0 ≤ start < end ≤ 50, in any order - ◆
Two ranges overlap if they share any time, including a single boundary point: [1, 4] and [4, 7] overlap - ◆
Combine every group of overlapping ranges into one range covering all of them - ◆
Return the combined ranges sorted by start; no two returned ranges overlap or touch
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Merging Any Overlapping Pair Until None Remain
BruteTreat the bookings as a pile of ranges. Scan every pair; the moment two overlap (a starts no later than b ends, and b starts no later than a ends), replace the pair with one range spanning both and start scanning again from the beginning — the new, wider range might now overlap ranges that were previously safe. Repeat until a full scan finds no overlapping pair, then sort what is left by start. Each scan can cost O(n²) and up to n − 1 merges may each trigger a fresh scan.
O(n³)O(n)1class Solution {
2 public int[][] combineBookings(int[][] bookings) {
3 List<int[]> ranges = new ArrayList<>();
4 for (int[] booking : bookings) ranges.add(new int[]{booking[0], booking[1]});
5 boolean merged = true;
6 while (merged) {
7 merged = false;
8 for (int i = 0; i < ranges.size() && !merged; i++) {
9 for (int j = i + 1; j < ranges.size(); j++) {
10 int[] a = ranges.get(i), b = ranges.get(j);
11 if (a[0] <= b[1] && b[0] <= a[1]) {
12 ranges.set(i, new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])});
13 ranges.remove(j);
14 merged = true;
15 break;
16 }
17 }
18 }
19 }
20 ranges.sort((a, b) -> a[0] - b[0]);
21 return ranges.toArray(new int[0][]);
22 }
23}Optimal — Sort by Start, Then Sweep Once
OptimalSort the ranges by start. Now any range that overlaps the range being built must appear right after it: keep one "current" range, and for each next range, if it starts at or before the current end, extend the current end to the larger of the two ends; otherwise the current range is finished — store it and start a new one. After the last range, store the final current one. Sorting dominates the cost; the sweep itself is a single pass.
O(n log n)O(n)1class Solution {
2 public int[][] combineBookings(int[][] bookings) {
3 int[][] sorted = bookings.clone();
4 Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
5 List<int[]> result = new ArrayList<>();
6 int[] current = {sorted[0][0], sorted[0][1]};
7 for (int i = 1; i < sorted.length; i++) {
8 if (sorted[i][0] <= current[1]) {
9 current[1] = Math.max(current[1], sorted[i][1]);
10 } else {
11 result.add(current);
12 current = new int[]{sorted[i][0], sorted[i][1]};
13 }
14 }
15 result.add(current);
16 return result.toArray(new int[0][]);
17 }
18}