Next Interval (Find Smallest Start ≥ End)

🎯

Next Interval (Find Smallest Start ≥ End)

hardHEAPAmazonGoogle

Imagine you have a list of meetings and want to find for each meeting the next meeting that starts right after it ends, to schedule back-to-back sessions efficiently.

💡 This problem involves intervals and requires finding the next interval whose start time is at least the end time of the current interval. Beginners often struggle because it’s not just sorting or scanning; it requires efficient lookups and pairing, which is why heaps are useful.

📋

Problem Statement

Given an array of intervals where each interval has a start and end time, for each interval find the index of the interval that has the smallest start time greater than or equal to the end time of the current interval. If no such interval exists, return -1 for that interval. Return the results as an array.

1 ≤ n ≤ 10^50 ≤ start_i, end_i ≤ 10^9Intervals may be unsortedIntervals may overlap

💡

Example

Input"[[2,3],[3,4],[5,6]]"

Output[1,2,-1]

For interval [2,3], next interval with start ≥ 3 is [3,4] at index 1. For [3,4], next interval with start ≥ 4 is [5,6] at index 2. For [5,6], no next interval exists, so -1.

• Single interval → output [-1]
• Intervals with same start and end → next interval could be itself or -1
• Intervals sorted in descending order → must still find correct next interval
• Intervals with large gaps → next interval might be far away or none

⚠️

Common Mistakes

Using linear search for each interval without sorting

Solution times out on large inputs

✅ Sort intervals and use binary search or heaps to optimize

Not storing original indices when sorting intervals

Output indices do not correspond to original intervals

✅ Store and return original indices alongside sorted intervals

Using min-heap instead of max-heap for two heaps approach

Logic breaks because we need to pop intervals with max end/start first

✅ Use max-heaps (or simulate with negative values) to get correct ordering

Not pushing back unused intervals into the start heap in two heaps approach

Some intervals get lost, leading to incorrect results

✅ After popping intervals from start heap, push back all except the chosen interval

Confusing start and end times in comparisons

Incorrect next interval indices returned

✅ Carefully compare start times with end times as per problem statement

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly comparing each interval with every other to find the next interval, which is simple but inefficient.

Intuition

For each interval, scan all other intervals to find the one with the smallest start time that is still greater than or equal to the current interval's end time.

Algorithm

1. Initialize an output array with -1 for all intervals.
2. For each interval i, iterate over all intervals j.
3. If interval j's start is ≥ interval i's end and is the smallest such start found so far, update output[i] to j.
4. Return the output array.

💡 The nested loops make it easy to understand but hard to scale; it’s a direct translation of the problem statement.

</>

Code

def find_next_intervals(intervals):
    n = len(intervals)
    result = [-1] * n
    for i in range(n):
        min_start = float('inf')
        for j in range(n):
            if intervals[j][0] >= intervals[i][1] and intervals[j][0] < min_start:
                min_start = intervals[j][0]
                result[i] = j
    return result

# Example usage
if __name__ == '__main__':
    intervals = [[2,3],[3,4],[5,6]]
    print(find_next_intervals(intervals))  # Output: [1, 2, -1]

Line Notes

n = len(intervals)Determine number of intervals to iterate over

result = [-1] * nInitialize result with -1 assuming no next interval found yet

for i in range(n)Outer loop picks current interval to find next interval for

for j in range(n)Inner loop checks all intervals against current interval

if intervals[j][0] >= intervals[i][1] and intervals[j][0] < min_startCheck if interval j starts after current interval ends and is the smallest such start

result[i] = jUpdate result with index of next interval

import java.util.*;
public class NextIntervalBruteForce {
    public static int[] findNextIntervals(int[][] intervals) {
        int n = intervals.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        for (int i = 0; i < n; i++) {
            int minStart = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < minStart) {
                    minStart = intervals[j][0];
                    result[i] = j;
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[][] intervals = {{2,3},{3,4},{5,6}};
        System.out.println(Arrays.toString(findNextIntervals(intervals)));
    }
}

Line Notes

int n = intervals.length;Get number of intervals for iteration

int[] result = new int[n];Create result array to store answers

Arrays.fill(result, -1);Initialize all results to -1 assuming no next interval

for (int i = 0; i < n; i++)Outer loop selects current interval

for (int j = 0; j < n; j++)Inner loop checks all intervals for next interval

if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < minStart)Find smallest start time ≥ current interval's end

result[i] = j;Update result with index of next interval

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

vector<int> findNextIntervals(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++) {
        int minStart = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < minStart) {
                minStart = intervals[j][0];
                result[i] = j;
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> intervals = {{2,3},{3,4},{5,6}};
    vector<int> res = findNextIntervals(intervals);
    for (int i : res) cout << i << ' ';
    cout << endl;
    return 0;
}

Line Notes

int n = intervals.size();Get number of intervals for iteration

vector<int> result(n, -1);Initialize result vector with -1

for (int i = 0; i < n; i++)Outer loop picks current interval

for (int j = 0; j < n; j++)Inner loop checks all intervals for next interval

if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < minStart)Find smallest start time ≥ current interval's end

result[i] = j;Update result with index of next interval

function findNextIntervals(intervals) {
    const n = intervals.length;
    const result = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        let minStart = Infinity;
        for (let j = 0; j < n; j++) {
            if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < minStart) {
                minStart = intervals[j][0];
                result[i] = j;
            }
        }
    }
    return result;
}

// Example usage
const intervals = [[2,3],[3,4],[5,6]];
console.log(findNextIntervals(intervals)); // Output: [1, 2, -1]

Line Notes

const n = intervals.length;Determine number of intervals

const result = new Array(n).fill(-1);Initialize result array with -1

for (let i = 0; i < n; i++)Outer loop selects current interval

for (let j = 0; j < n; j++)Inner loop checks all intervals for next interval

if (intervals[j][0] >= intervals[i][1] && intervals[j][0] < minStart)Find smallest start time ≥ current interval's end

result[i] = j;Update result with index of next interval

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We check every pair of intervals, so n intervals times n intervals = n^2 operations. Result array uses O(n) space.

💡 For n=20, this means 400 comparisons, which is manageable, but for n=100000, 10 billion comparisons is too slow.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Sorting + Binary Search

💡 This approach improves efficiency by sorting intervals by start time and using binary search to find the next interval, reducing the search from O(n) to O(log n) per interval.

Intuition

Sort intervals by their start time. For each interval, binary search to find the smallest start time that is ≥ the current interval's end time.

Algorithm

1. Create a list of (start, index) pairs and sort it by start time.
2. For each interval, binary search in the sorted list to find the smallest start ≥ interval's end.
3. If found, record the index of that interval; otherwise, record -1.
4. Return the result array.

💡 Sorting and binary search reduce the nested loops to a single loop with a log factor, making it scalable.

</>

Code

import bisect

def find_next_intervals(intervals):
    n = len(intervals)
    starts = sorted((interval[0], i) for i, interval in enumerate(intervals))
    result = [-1] * n
    for i, (start, end) in enumerate(intervals):
        idx = bisect.bisect_left(starts, (end, -1))
        if idx < n:
            result[i] = starts[idx][1]
    return result

# Example usage
if __name__ == '__main__':
    intervals = [[2,3],[3,4],[5,6]]
    print(find_next_intervals(intervals))  # Output: [1, 2, -1]

Line Notes

starts = sorted((interval[0], i) for i, interval in enumerate(intervals))Sort intervals by start time with original indices

result = [-1] * nInitialize result array with -1

for i, (start, end) in enumerate(intervals)Iterate over original intervals

idx = bisect.bisect_left(starts, (end, -1))Binary search for smallest start ≥ current interval's end

if idx < nCheck if binary search found a valid interval

result[i] = starts[idx][1]Record index of next interval

import java.util.*;

public class NextIntervalBinarySearch {
    public static int[] findNextIntervals(int[][] intervals) {
        int n = intervals.length;
        int[][] starts = new int[n][2];
        for (int i = 0; i < n; i++) {
            starts[i][0] = intervals[i][0];
            starts[i][1] = i;
        }
        Arrays.sort(starts, Comparator.comparingInt(a -> a[0]));
        int[] result = new int[n];
        Arrays.fill(result, -1);
        for (int i = 0; i < n; i++) {
            int target = intervals[i][1];
            int idx = binarySearch(starts, target);
            if (idx != -1) result[i] = starts[idx][1];
        }
        return result;
    }

    private static int binarySearch(int[][] starts, int target) {
        int left = 0, right = starts.length - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (starts[mid][0] >= target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] intervals = {{2,3},{3,4},{5,6}};
        System.out.println(Arrays.toString(findNextIntervals(intervals)));
    }
}

Line Notes

int[][] starts = new int[n][2];Create array to store start times and original indices

Arrays.sort(starts, Comparator.comparingInt(a -> a[0]));Sort intervals by start time

Arrays.fill(result, -1);Initialize result array with -1

for (int i = 0; i < n; i++)Iterate over original intervals

int idx = binarySearch(starts, target);Find smallest start ≥ end using binary search

if (idx != -1) result[i] = starts[idx][1];Update result if valid next interval found

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binarySearch(const vector<pair<int,int>>& starts, int target) {
    int left = 0, right = (int)starts.size() - 1, ans = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (starts[mid].first >= target) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

vector<int> findNextIntervals(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<pair<int,int>> starts;
    for (int i = 0; i < n; i++) {
        starts.emplace_back(intervals[i][0], i);
    }
    sort(starts.begin(), starts.end());
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++) {
        int idx = binarySearch(starts, intervals[i][1]);
        if (idx != -1) result[i] = starts[idx].second;
    }
    return result;
}

int main() {
    vector<vector<int>> intervals = {{2,3},{3,4},{5,6}};
    vector<int> res = findNextIntervals(intervals);
    for (int i : res) cout << i << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<pair<int,int>> starts;Store start times with original indices

sort(starts.begin(), starts.end());Sort intervals by start time

vector<int> result(n, -1);Initialize result vector with -1

for (int i = 0; i < n; i++)Iterate over original intervals

int idx = binarySearch(starts, intervals[i][1]);Binary search for smallest start ≥ end

if (idx != -1) result[i] = starts[idx].second;Update result if next interval found

function binarySearch(starts, target) {
    let left = 0, right = starts.length - 1, ans = -1;
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (starts[mid][0] >= target) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

function findNextIntervals(intervals) {
    const n = intervals.length;
    const starts = intervals.map((interval, i) => [interval[0], i]);
    starts.sort((a, b) => a[0] - b[0]);
    const result = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        const idx = binarySearch(starts, intervals[i][1]);
        if (idx !== -1) result[i] = starts[idx][1];
    }
    return result;
}

// Example usage
const intervals = [[2,3],[3,4],[5,6]];
console.log(findNextIntervals(intervals)); // Output: [1, 2, -1]

Line Notes

const starts = intervals.map((interval, i) => [interval[0], i]);Create array of start times with indices

starts.sort((a, b) => a[0] - b[0]);Sort intervals by start time

const result = new Array(n).fill(-1);Initialize result array with -1

for (let i = 0; i < n; i++)Iterate over original intervals

const idx = binarySearch(starts, intervals[i][1]);Binary search for smallest start ≥ end

if (idx !== -1) result[i] = starts[idx][1];Update result if next interval found

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n), and binary searching for each interval takes O(n log n), total O(n log n). Space is O(n) for storing starts and result.

💡 For n=100000, this approach performs about 2 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted / Efficient for large inputs

This approach is a common interview solution balancing clarity and efficiency.

🧠

Optimal Two Heaps Approach

💡 This approach uses two max-heaps to efficiently find the next interval by pairing intervals based on their start and end times, avoiding binary search and enabling O(n log n) time with a different data structure.

Intuition

Use two max-heaps: one for intervals sorted by start time, one for intervals sorted by end time. For each interval popped from end heap, find the interval with the smallest start time ≥ its end by popping from start heap.

Algorithm

1. Build two max-heaps: one for start times with indices, one for end times with indices.
2. Initialize result array with -1.
3. While end heap is not empty, pop the top interval (with max end).
4. Pop from start heap intervals with start ≥ popped end, track the one with smallest start.
5. Assign the index of that interval as the next interval for the popped interval.
6. Push back any popped start intervals not used except the chosen one.
7. Return the result array.

💡 The two heaps allow pairing intervals by comparing max end and max start efficiently, avoiding scanning or binary searching for each interval.

</>

Code

import heapq

def find_next_intervals(intervals):
    n = len(intervals)
    result = [-1] * n
    max_start_heap = []
    max_end_heap = []

    for i, (start, end) in enumerate(intervals):
        heapq.heappush(max_start_heap, (-start, i))
        heapq.heappush(max_end_heap, (-end, i))

    while max_end_heap:
        end, end_idx = heapq.heappop(max_end_heap)
        end = -end

        if not max_start_heap or -max_start_heap[0][0] < end:
            continue

        # Pop all intervals with start >= end, track the one with smallest start
        candidates = []
        while max_start_heap and -max_start_heap[0][0] >= end:
            start, start_idx = heapq.heappop(max_start_heap)
            candidates.append((start, start_idx))

        # Find the candidate with smallest start (largest negative start)
        best = max(candidates, key=lambda x: x[0])  # max negative start = smallest start

        result[end_idx] = best[1]

        # Push back all candidates except the chosen one
        for c in candidates:
            if c != best:
                heapq.heappush(max_start_heap, c)

    return result

# Example usage
if __name__ == '__main__':
    intervals = [[2,3],[3,4],[5,6]]
    print(find_next_intervals(intervals))  # Output: [1, 2, -1]

Line Notes

result = [-1] * nInitialize result array with -1 assuming no next interval

max_start_heap = []Heap to store intervals by start time (max heap simulated with negative values)

max_end_heap = []Heap to store intervals by end time (max heap simulated with negative values)

heapq.heappush(max_start_heap, (-start, i))Push negative start to simulate max heap

heapq.heappush(max_end_heap, (-end, i))Push negative end to simulate max heap

end, end_idx = heapq.heappop(max_end_heap)Pop interval with max end time

if not max_start_heap or -max_start_heap[0][0] < end: continueIf max start is less than current end, no next interval possible

while max_start_heap and -max_start_heap[0][0] >= endPop intervals with start ≥ current end to find candidates

best = max(candidates, key=lambda x: x[0])Select candidate with smallest start (largest negative start)

result[end_idx] = best[1]Assign next interval index

for c in candidates: if c != best: heapq.heappush(max_start_heap, c)Push back all other candidates for future matches

import java.util.*;

public class NextIntervalTwoHeaps {
    public static int[] findNextIntervals(int[][] intervals) {
        int n = intervals.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);

        PriorityQueue<int[]> maxStartHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);
        PriorityQueue<int[]> maxEndHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);

        for (int i = 0; i < n; i++) {
            maxStartHeap.offer(new int[]{intervals[i][0], i});
            maxEndHeap.offer(new int[]{intervals[i][1], i});
        }

        while (!maxEndHeap.isEmpty()) {
            int[] topEnd = maxEndHeap.poll();
            int end = topEnd[0];
            int endIdx = topEnd[1];

            if (maxStartHeap.isEmpty() || maxStartHeap.peek()[0] < end) {
                continue;
            }

            List<int[]> candidates = new ArrayList<>();
            while (!maxStartHeap.isEmpty() && maxStartHeap.peek()[0] >= end) {
                candidates.add(maxStartHeap.poll());
            }

            int[] best = candidates.get(0);
            for (int[] c : candidates) {
                if (c[0] < best[0]) {
                    best = c;
                }
            }

            result[endIdx] = best[1];

            for (int[] c : candidates) {
                if (c != best) {
                    maxStartHeap.offer(c);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] intervals = {{2,3},{3,4},{5,6}};
        System.out.println(Arrays.toString(findNextIntervals(intervals)));
    }
}

Line Notes

int[] result = new int[n];Initialize result array

Arrays.fill(result, -1);Fill result with -1 assuming no next interval

PriorityQueue<int[]> maxStartHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);Max heap for start times

PriorityQueue<int[]> maxEndHeap = new PriorityQueue<>((a,b) -> b[0] - a[0]);Max heap for end times

maxStartHeap.offer(new int[]{intervals[i][0], i});Add start time and index to start heap

maxEndHeap.offer(new int[]{intervals[i][1], i});Add end time and index to end heap

int[] topEnd = maxEndHeap.poll();Pop interval with max end time

if (maxStartHeap.isEmpty() || maxStartHeap.peek()[0] < end)If no start interval ≥ end, continue

while (!maxStartHeap.isEmpty() && maxStartHeap.peek()[0] >= end)Pop intervals with start ≥ end to find candidates

int[] best = candidates.get(0); for (int[] c : candidates) { if (c[0] < best[0]) best = c; }Find candidate with smallest start

result[endIdx] = best[1];Assign next interval index

for (int[] c : candidates) { if (c != best) maxStartHeap.offer(c); }Push back other candidates

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> findNextIntervals(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<int> result(n, -1);

    priority_queue<pair<int,int>> maxStartHeap;
    priority_queue<pair<int,int>> maxEndHeap;

    for (int i = 0; i < n; i++) {
        maxStartHeap.push({intervals[i][0], i});
        maxEndHeap.push({intervals[i][1], i});
    }

    while (!maxEndHeap.empty()) {
        auto [end, endIdx] = maxEndHeap.top(); maxEndHeap.pop();

        if (maxStartHeap.empty() || maxStartHeap.top().first < end) {
            continue;
        }

        vector<pair<int,int>> candidates;
        while (!maxStartHeap.empty() && maxStartHeap.top().first >= end) {
            candidates.push_back(maxStartHeap.top());
            maxStartHeap.pop();
        }

        auto best = candidates[0];
        for (auto& c : candidates) {
            if (c.first < best.first) {
                best = c;
            }
        }

        result[endIdx] = best.second;

        for (auto& c : candidates) {
            if (c != best) {
                maxStartHeap.push(c);
            }
        }
    }

    return result;
}

int main() {
    vector<vector<int>> intervals = {{2,3},{3,4},{5,6}};
    vector<int> res = findNextIntervals(intervals);
    for (int i : res) cout << i << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> result(n, -1);Initialize result vector with -1

priority_queue<pair<int,int>> maxStartHeap;Max heap for start times

priority_queue<pair<int,int>> maxEndHeap;Max heap for end times

maxStartHeap.push({intervals[i][0], i});Push start time and index

maxEndHeap.push({intervals[i][1], i});Push end time and index

auto [end, endIdx] = maxEndHeap.top(); maxEndHeap.pop();Pop interval with max end

if (maxStartHeap.empty() || maxStartHeap.top().first < end)No start interval ≥ end, skip

while (!maxStartHeap.empty() && maxStartHeap.top().first >= end)Pop intervals with start ≥ end to find candidates

auto best = candidates[0]; for (auto& c : candidates) { if (c.first < best.first) best = c; }Find candidate with smallest start

result[endIdx] = best.second;Assign next interval index

for (auto& c : candidates) { if (c != best) maxStartHeap.push(c); }Push back other candidates

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
    push(val) {
        this.heap.push(val);
        let i = this.heap.length - 1;
        while (i > 0 && this.heap[this.parent(i)][0] < this.heap[i][0]) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 0) return null;
        const top = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.heapify(0);
        }
        return top;
    }
    heapify(i) {
        let largest = i;
        const left = this.left(i);
        const right = this.right(i);
        if (left < this.heap.length && this.heap[left][0] > this.heap[largest][0]) largest = left;
        if (right < this.heap.length && this.heap[right][0] > this.heap[largest][0]) largest = right;
        if (largest !== i) {
            this.swap(i, largest);
            this.heapify(largest);
        }
    }
    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }
    isEmpty() {
        return this.heap.length === 0;
    }
}

function findNextIntervals(intervals) {
    const n = intervals.length;
    const result = new Array(n).fill(-1);
    const maxStartHeap = new MaxHeap();
    const maxEndHeap = new MaxHeap();

    for (let i = 0; i < n; i++) {
        maxStartHeap.push([intervals[i][0], i]);
        maxEndHeap.push([intervals[i][1], i]);
    }

    while (!maxEndHeap.isEmpty()) {
        const [end, endIdx] = maxEndHeap.pop();

        if (maxStartHeap.isEmpty() || maxStartHeap.peek()[0] < end) {
            continue;
        }

        const candidates = [];
        while (!maxStartHeap.isEmpty() && maxStartHeap.peek()[0] >= end) {
            candidates.push(maxStartHeap.pop());
        }

        let best = candidates[0];
        for (const c of candidates) {
            if (c[0] < best[0]) {
                best = c;
            }
        }

        result[endIdx] = best[1];

        for (const c of candidates) {
            if (c !== best) {
                maxStartHeap.push(c);
            }
        }
    }

    return result;
}

// Example usage
const intervals = [[2,3],[3,4],[5,6]];
console.log(findNextIntervals(intervals)); // Output: [1, 2, -1]

Line Notes

const result = new Array(n).fill(-1);Initialize result array with -1

const maxStartHeap = new MaxHeap();Max heap for start times

const maxEndHeap = new MaxHeap();Max heap for end times

maxStartHeap.push([intervals[i][0], i]);Push start time and index

maxEndHeap.push([intervals[i][1], i]);Push end time and index

const [end, endIdx] = maxEndHeap.pop();Pop interval with max end

if (maxStartHeap.isEmpty() || maxStartHeap.peek()[0] < end)No start interval ≥ end, skip

while (!maxStartHeap.isEmpty() && maxStartHeap.peek()[0] >= end)Pop intervals with start ≥ end to find candidates

let best = candidates[0]; for (const c of candidates) { if (c[0] < best[0]) best = c; }Find candidate with smallest start

result[endIdx] = best[1];Assign next interval index

for (const c of candidates) { if (c !== best) maxStartHeap.push(c); }Push back other candidates

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Building heaps takes O(n), each interval is pushed and popped at most once from heaps, total O(n log n). Space is O(n) for heaps and result.

💡 This approach is optimal and uses heaps to efficiently pair intervals, suitable for large inputs.

Interview Verdict: Accepted / Optimal

This is the best approach to implement in interviews for this problem, demonstrating mastery of heaps and interval pairing.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the two heaps approach in 95% of interviews for this problem because it is optimal and demonstrates strong data structure knowledge.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Sorting + Binary Search	O(n log n)	O(n)	No	N/A	Good fallback if heaps are unfamiliar
3. Two Heaps	O(n log n)	O(n)	No	N/A	Optimal approach to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know how to present your solution clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss sorting + binary search to improve efficiency.Step 4: Present the optimal two heaps approach as the best solution.Step 5: Code the optimal approach and test with examples.

Time Allocation

Clarify: 3min → Approach discussion: 5min → Code: 10min → Testing & optimization: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of interval pairing, efficient searching, and your ability to use heaps or binary search to optimize.

Common Follow-ups

• What if intervals are very large or sparse? → Use efficient data structures like heaps or balanced trees.
• Can you find the next interval with start strictly greater than end? → Modify comparison operators accordingly.

💡 Follow-ups test your flexibility in adapting the solution to variations and understanding of data structures.

🔍

Pattern Recognition

When to Use

1) Problem involves intervals, 2) Need to find next interval with start ≥ end, 3) Efficient lookup required, 4) Pairing intervals by start and end times.

Signature Phrases

next intervalsmallest start ≥ endinterval scheduling with two heaps

NOT This Pattern When

Problems that only require sorting intervals or greedy scheduling without pairing next intervals.

Similar Problems

Merge Intervals - merging overlapping intervalsMinimum Number of Arrows to Burst Balloons - interval coverageEmployee Free Time - interval intersection

Practice

1. You are given schedules of multiple employees, each with their working intervals. You want to find all common free time intervals where no employee is working. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach to pick intervals with earliest end times and find gaps between them.

B. Flatten all intervals from all employees, sort them by start time, then merge overlapping intervals to find gaps.

C. Use dynamic programming to track overlapping intervals and compute free times.

D. Use a min-heap to iteratively merge intervals from each employee's schedule.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding common free intervals across multiple employees, which means merging all intervals to identify gaps.

2. Step 2: Evaluate approaches

   Greedy earliest end time (A) does not guarantee merging all intervals correctly. DP (C) is unnecessary and inefficient here. Min-heap merging (D) is a valid approach but more complex than flattening and sorting. Flattening and sorting all intervals (B) ensures all intervals are processed in order, enabling correct gap detection.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Flattening and sorting all intervals is the canonical approach for interval merging [OK]

Hint: Flatten and sort all intervals to find gaps [OK]

Common Mistakes:

• Assuming greedy earliest end time works for merging intervals
• Confusing DP with interval merging
• Thinking min-heap is always simpler

2. What is the time complexity of the optimal algorithm that sorts engineers by efficiency and uses a min-heap to maintain speeds when selecting a team of size at most k from n engineers?

medium

A. O(n log n) due to sorting and heap operations on at most k elements

B. O(n^2) because for each engineer we might compare with all others in the heap

C. O(n * k) because each engineer is processed and heap operations take O(k)

D. O(k log n) since heap operations dominate and depend on n

Solution

1. Step 1: Identify sorting cost

   Sorting n engineers by efficiency takes O(n log n).

2. Step 2: Analyze heap operations

   Each engineer is pushed into a min-heap of size at most k, so each push/pop is O(log k). Since k ≤ n, heap operations total O(n log k).

3. Step 3: Combine complexities

   Total time is O(n log n + n log k). Since k ≤ n, this simplifies to O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting dominates, heap operations are logarithmic in k [OK]

Hint: Sorting dominates; heap ops are O(log k) per element [OK]

Common Mistakes:

• Confusing heap size with n
• Assuming heap ops are O(k) not O(log k)
• Ignoring sorting cost

3. The following code attempts to rearrange a string so that the same characters are at least k distance apart. Identify the line containing the subtle bug that can cause invalid output or failure.

medium

A. Line: heapq.heapify(max_heap) # heapify should be replaced with sort

B. Line: if k == 0: return s # should handle k=1 differently

C. Line: queue.append((char, count)) # decrement count missing

D. Line: if front_count < 0: heapq.heappush(max_heap, (front_count, front_char)) # should check for <= 0

Solution

1. Step 1: Identify decrement of count

   The algorithm must decrement the count of the character after using it, i.e., count + 1 since counts are negative.

2. Step 2: Locate missing decrement

   In the buggy line, count is appended without incrementing, so the character count never decreases, causing infinite loops or invalid results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct decrement is critical to track usage [OK]

Hint: Check if character count is updated after usage [OK]

Common Mistakes:

• Forgetting to decrement count after popping from heap
• Misusing queue length to enforce k-distance
• Incorrect heap operations or conditions

4. What is the time complexity of the optimal balanced two heaps approach for the sliding window median problem with input size n and window size k?

medium

A. O(n log k)

B. O(n * k log k)

C. O(n log n)

D. O(n * k)

Solution

1. Step 1: Identify operations per element

   Each element is inserted and removed once from heaps, each operation O(log k).

2. Step 2: Calculate total complexity

   For n elements, total time is O(n log k), better than brute force O(n k log k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Logarithmic heap operations per element yield O(n log k) [OK]

Hint: Heap operations cost O(log k) per element [OK]

Common Mistakes:

• Confusing k with n in complexity
• Assuming sorting each window is optimal
• Ignoring heap balancing cost

5. What is the time complexity of the optimized task scheduler algorithm that uses a hash map to track the next available day for each task, given n tasks and cooldown space?

medium

A. O(n * space) due to iterating over cooldown days for each task

B. O(n) because each task is processed once with O(1) hash map operations

C. O(n log n) due to sorting tasks or heap operations

D. O(n^2) because of nested loops checking cooldown constraints

Solution

1. Step 1: Identify operations per task

   Each task is processed once in a single loop over the tasks array.

2. Step 2: Analyze hash map operations

   Hash map lookups and updates for next_available are O(1) on average, so no nested loops or sorting involved.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with O(1) lookups -> O(n) time -> [OK]

Hint: Hash map lookups are O(1), no nested loops -> O(n) [OK]

Common Mistakes:

• Assuming cooldown causes nested loops increasing complexity
• Confusing with heap-based solutions that are O(n log n)
• Thinking space affects time complexity linearly