Narrowest Window That Touches Every Schedule
Solve this ProblemSeveral teams each publish a sorted list of available time slots. Find the narrowest window [lo, hi] that contains at least one slot from every team, where "narrowest" means the smallest hi − lo (ties go to the window with the smaller lo). All teams publish the same number of slots.
Trying every slot as a left edge and re-scanning each team's list works but repeats a lot of work. Instead, keep a min-heap holding one current slot per team: the heap root is always the left edge of the best window still possible, and the largest current slot is its right edge. Advancing only the team that owns the smallest slot shrinks the window step by step.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ schedules.length ≤ 5, and every schedule has the same length, 1 ≤ schedules[i].length ≤ 6 - ◆
-50 ≤ schedules[i][j] ≤ 50, and every schedule is sorted in non-decreasing order - ◆
Return [lo, hi], the narrowest window with at least one value from every schedule inside it (lo ≤ value ≤ hi); "narrowest" means the smallest hi − lo - ◆
If several windows are equally narrow, return the one with the smaller lo
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Value as the Left Edge
BruteEvery candidate window has some value as its left edge, so try each of the N = k × m values in turn. For a given left edge lo, the best right edge is the largest of "the smallest value ≥ lo" taken from each schedule — found here by scanning each schedule from its start. If some schedule has no value ≥ lo, that left edge is impossible. Keep the narrowest window, preferring the smaller lo on ties. Correct, but every one of the N left edges re-scans all k schedules from scratch.
O(N · k · m)O(1)1class Solution {
2 public int[] narrowestWindow(int[][] schedules) {
3 int k = schedules.length, m = schedules[0].length;
4 boolean found = false;
5 int bestLo = 0, bestHi = 0;
6 for (int r = 0; r < k; r++) {
7 for (int c = 0; c < m; c++) {
8 int lo = schedules[r][c];
9 int hi = lo;
10 boolean ok = true;
11 for (int other = 0; other < k && ok; other++) {
12 int idx = 0;
13 while (idx < m && schedules[other][idx] < lo) idx++;
14 if (idx == m) ok = false;
15 else hi = Math.max(hi, schedules[other][idx]);
16 }
17 if (ok && (!found || hi - lo < bestHi - bestLo || (hi - lo == bestHi - bestLo && lo < bestLo))) {
18 found = true;
19 bestLo = lo;
20 bestHi = hi;
21 }
22 }
23 }
24 return new int[]{bestLo, bestHi};
25 }
26}Optimal — Min-Heap of One Pointer per Schedule
OptimalKeep exactly one "current value" per schedule (initially each schedule's first) in a min-heap, and remember the largest of them, currentMax. The heap root is the smallest current value, so [root, currentMax] is the narrowest window that can start at the current root. Record it if it beats the best so far, then advance the schedule the root came from to its next value (updating currentMax). Repeat until a schedule runs out. Each of the N values enters the heap once at O(log k), instead of being rescanned from scratch.
O(N log k)O(k)1class Solution {
2 public int[] narrowestWindow(int[][] schedules) {
3 int k = schedules.length, m = schedules[0].length;
4 PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
5 int currentMax = Integer.MIN_VALUE;
6 for (int r = 0; r < k; r++) {
7 heap.offer(new int[]{schedules[r][0], r, 0});
8 currentMax = Math.max(currentMax, schedules[r][0]);
9 }
10 int bestLo = heap.peek()[0], bestHi = currentMax;
11 while (true) {
12 int[] smallest = heap.poll();
13 if (currentMax - smallest[0] < bestHi - bestLo) {
14 bestLo = smallest[0];
15 bestHi = currentMax;
16 }
17 if (smallest[2] + 1 == m) break;
18 int next = schedules[smallest[1]][smallest[2] + 1];
19 heap.offer(new int[]{next, smallest[1], smallest[2] + 1});
20 currentMax = Math.max(currentMax, next);
21 }
22 return new int[]{bestLo, bestHi};
23 }
24}