Bird
Raised Fist0
Interview PrepintervalshardAmazonGoogle

Minimum Interval to Include Each Query

Choose your preparation mode4 modes available
🎯
Minimum Interval to Include Each Query
hardINTERVALSAmazonGoogle

Imagine you have a set of time intervals representing TV shows and a list of times you want to watch. For each time, you want to find the shortest show that is playing at that moment.

💡 This problem involves intervals and queries, which can confuse beginners because it requires combining sorting, searching, and efficient data structures. Beginners often struggle to efficiently find the minimum interval covering each query without checking all intervals repeatedly.
📋
Problem Statement

Given a list of intervals where each interval is represented as [start, end], and a list of queries, for each query find the length of the smallest interval that includes the query point. If no such interval exists, return -1 for that query.

1 ≤ number of intervals ≤ 10^51 ≤ number of queries ≤ 10^50 ≤ start_i ≤ end_i ≤ 10^70 ≤ queries[i] ≤ 10^7
💡
Example
Input"intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]"
Output[3,3,1,4]

For query 2, intervals [1,4], [2,4], and [3,6] include 2; smallest length is 3 ([2,4]). For 3, smallest is also length 3 ([2,4]). For 4, smallest is length 1 ([4,4]). For 5, only [3,6] includes it, length 4.

  • No intervals at all → all queries return -1
  • Queries outside all intervals → return -1
  • Intervals with same start and end (zero length) → must handle correctly
  • Multiple intervals covering query with same length → return that length
⚠️
Common Mistakes
Not sorting queries and intervals before processing

Leads to incorrect or inefficient results because intervals and queries are processed out of order

✅ Always sort intervals by start and queries by value before processing

Not removing intervals from heap that ended before the query

Heap contains stale intervals, causing wrong minimum interval length results

✅ Pop intervals from heap while their end < current query

Mixing up interval length calculation (off by one)

Incorrect interval length leads to wrong minimum length answers

✅ Calculate length as end - start + 1 consistently

Not preserving original query indices when sorting queries

Results get assigned to wrong queries, causing incorrect output order

✅ Store original indices with queries before sorting and restore order after processing

Using inefficient coverage check in binary search approach

Causes timeouts on large inputs due to O(n) coverage checks per query

✅ Use more advanced data structures or prefer heap approach for efficiency

🧠
Brute Force (Check Each Interval for Each Query)
💡 This approach exists to build intuition by directly implementing the problem statement. It is simple but inefficient, helping beginners understand the problem deeply before optimizing.

Intuition

For each query, check every interval to see if it includes the query. Track the minimum length among those intervals.

Algorithm

  1. Initialize an answer array with -1 for each query.
  2. For each query, iterate over all intervals.
  3. If the interval covers the query, update the answer with the minimum interval length found.
  4. Return the answer array.
💡 This algorithm is straightforward but inefficient because it checks all intervals for every query, leading to repeated work.
</>
Code
from typing import List

def min_interval_brute_force(intervals: List[List[int]], queries: List[int]) -> List[int]:
    res = []
    for q in queries:
        min_len = float('inf')
        for start, end in intervals:
            if start <= q <= end:
                length = end - start + 1
                if length < min_len:
                    min_len = length
        res.append(min_len if min_len != float('inf') else -1)
    return res

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[2,4],[3,6],[4,4]]
    queries = [2,3,4,5]
    print(min_interval_brute_force(intervals, queries))  # Output: [3,3,1,4]
Line Notes
for q in queries:Outer loop iterates over each query to find its minimum covering interval
for start, end in intervals:Inner loop checks every interval for coverage of the current query
if start <= q <= end:Check if the query lies within the current interval
res.append(min_len if min_len != float('inf') else -1)Append the smallest interval length found or -1 if none covers the query
import java.util.*;

public class MinIntervalBruteForce {
    public static int[] minInterval(int[][] intervals, int[] queries) {
        int[] res = new int[queries.length];
        Arrays.fill(res, -1);
        for (int i = 0; i < queries.length; i++) {
            int q = queries[i];
            int minLen = Integer.MAX_VALUE;
            for (int[] interval : intervals) {
                if (interval[0] <= q && q <= interval[1]) {
                    int length = interval[1] - interval[0] + 1;
                    if (length < minLen) {
                        minLen = length;
                    }
                }
            }
            if (minLen != Integer.MAX_VALUE) res[i] = minLen;
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{2,4},{3,6},{4,4}};
        int[] queries = {2,3,4,5};
        System.out.println(Arrays.toString(minInterval(intervals, queries)));
    }
}
Line Notes
for (int i = 0; i < queries.length; i++) {Loop over each query index to process queries sequentially
for (int[] interval : intervals) {Check every interval for coverage of the current query
if (interval[0] <= q && q <= interval[1]) {Verify if query lies inside the interval
if (minLen != Integer.MAX_VALUE) res[i] = minLen;Update result only if a covering interval was found
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

vector<int> minIntervalBruteForce(vector<vector<int>>& intervals, vector<int>& queries) {
    vector<int> res;
    for (int q : queries) {
        int minLen = INT_MAX;
        for (auto& interval : intervals) {
            if (interval[0] <= q && q <= interval[1]) {
                int length = interval[1] - interval[0] + 1;
                if (length < minLen) {
                    minLen = length;
                }
            }
        }
        res.push_back(minLen == INT_MAX ? -1 : minLen);
    }
    return res;
}

int main() {
    vector<vector<int>> intervals = {{1,4},{2,4},{3,6},{4,4}};
    vector<int> queries = {2,3,4,5};
    vector<int> result = minIntervalBruteForce(intervals, queries);
    for (int val : result) cout << val << ' ';
    cout << endl;
    return 0;
}
Line Notes
for (int q : queries) {Iterate over each query to find minimum covering interval
for (auto& interval : intervals) {Check all intervals for coverage of current query
if (interval[0] <= q && q <= interval[1]) {Condition to verify if query lies inside interval
res.push_back(minLen == INT_MAX ? -1 : minLen);Store minimum length or -1 if none found
function minIntervalBruteForce(intervals, queries) {
    const res = [];
    for (const q of queries) {
        let minLen = Infinity;
        for (const [start, end] of intervals) {
            if (start <= q && q <= end) {
                const length = end - start + 1;
                if (length < minLen) minLen = length;
            }
        }
        res.push(minLen === Infinity ? -1 : minLen);
    }
    return res;
}

// Test
const intervals = [[1,4],[2,4],[3,6],[4,4]];
const queries = [2,3,4,5];
console.log(minIntervalBruteForce(intervals, queries)); // [3,3,1,4]
Line Notes
for (const q of queries) {Loop over each query to find smallest covering interval
for (const [start, end] of intervals) {Check every interval for coverage of current query
if (start <= q && q <= end) {Check if query lies inside the interval
res.push(minLen === Infinity ? -1 : minLen);Push smallest interval length or -1 if none found
⏱
Complexity
TimeO(n * m)
SpaceO(m)

For each of the m queries, we check all n intervals, resulting in O(n*m) time. Space is O(m) for the output.

💡 If n and m are 100,000, this means 10 billion operations, which is too slow for interviews.
Interview Verdict: TLE

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

🧠
Sorting Intervals and Queries + Min-Heap for Active Intervals
💡 This approach improves efficiency by sorting intervals and queries, then using a min-heap to track active intervals covering queries. It introduces a common pattern of processing events in sorted order.

Intuition

Sort intervals by start time and queries by value. Use a min-heap to keep track of intervals that cover the current query, removing intervals that ended before the query. The top of the heap gives the smallest interval covering the query.

Algorithm

  1. Sort intervals by their start time.
  2. Sort queries along with their original indices.
  3. Initialize a min-heap to store intervals by their length and end time.
  4. Iterate over queries in ascending order:
  5. Add all intervals starting before or at the query to the heap.
  6. Remove intervals from the heap that end before the query.
  7. The top of the heap (if any) is the smallest interval covering the query.
  8. Fill the answer array accordingly.
💡 This algorithm cleverly uses sorting and a heap to avoid checking all intervals for each query, drastically reducing redundant work.
</>
Code
from typing import List
import heapq

def min_interval_heap(intervals: List[List[int]], queries: List[int]) -> List[int]:
    intervals.sort(key=lambda x: x[0])
    sorted_queries = sorted((q, i) for i, q in enumerate(queries))
    res = [-1] * len(queries)
    min_heap = []  # stores (length, end)
    i = 0
    for q, idx in sorted_queries:
        while i < len(intervals) and intervals[i][0] <= q:
            start, end = intervals[i]
            length = end - start + 1
            heapq.heappush(min_heap, (length, end))
            i += 1
        while min_heap and min_heap[0][1] < q:
            heapq.heappop(min_heap)
        res[idx] = min_heap[0][0] if min_heap else -1
    return res

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[2,4],[3,6],[4,4]]
    queries = [2,3,4,5]
    print(min_interval_heap(intervals, queries))  # Output: [3,3,1,4]
Line Notes
intervals.sort(key=lambda x: x[0])Sort intervals by start to process them in order
sorted_queries = sorted((q, i) for i, q in enumerate(queries))Sort queries but keep original indices for result placement
while i < len(intervals) and intervals[i][0] <= q:Add all intervals starting before or at current query to heap
while min_heap and min_heap[0][1] < q:Remove intervals from heap that ended before current query
import java.util.*;

public class MinIntervalHeap {
    public static int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int n = queries.length;
        int[][] sortedQueries = new int[n][2];
        for (int i = 0; i < n; i++) {
            sortedQueries[i][0] = queries[i];
            sortedQueries[i][1] = i;
        }
        Arrays.sort(sortedQueries, Comparator.comparingInt(a -> a[0]));
        int[] res = new int[n];
        Arrays.fill(res, -1);
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int i = 0;
        for (int[] q : sortedQueries) {
            int query = q[0], idx = q[1];
            while (i < intervals.length && intervals[i][0] <= query) {
                int length = intervals[i][1] - intervals[i][0] + 1;
                minHeap.offer(new int[]{length, intervals[i][1]});
                i++;
            }
            while (!minHeap.isEmpty() && minHeap.peek()[1] < query) {
                minHeap.poll();
            }
            res[idx] = minHeap.isEmpty() ? -1 : minHeap.peek()[0];
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{2,4},{3,6},{4,4}};
        int[] queries = {2,3,4,5};
        System.out.println(Arrays.toString(minInterval(intervals, queries)));
    }
}
Line Notes
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));Sort intervals by start time for ordered processing
Arrays.sort(sortedQueries, Comparator.comparingInt(a -> a[0]));Sort queries by value while tracking original indices
while (i < intervals.length && intervals[i][0] <= query) {Add intervals starting before or at query to min-heap
while (!minHeap.isEmpty() && minHeap.peek()[1] < query) {Remove intervals from heap that ended before query
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> minIntervalHeap(vector<vector<int>>& intervals, vector<int>& queries) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[0] < b[0]; });
    int n = queries.size();
    vector<pair<int,int>> sortedQueries;
    for (int i = 0; i < n; i++) sortedQueries.emplace_back(queries[i], i);
    sort(sortedQueries.begin(), sortedQueries.end());
    vector<int> res(n, -1);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> minHeap; // (length, end)
    int i = 0;
    for (auto& [q, idx] : sortedQueries) {
        while (i < (int)intervals.size() && intervals[i][0] <= q) {
            int length = intervals[i][1] - intervals[i][0] + 1;
            minHeap.emplace(length, intervals[i][1]);
            i++;
        }
        while (!minHeap.empty() && minHeap.top().second < q) {
            minHeap.pop();
        }
        res[idx] = minHeap.empty() ? -1 : minHeap.top().first;
    }
    return res;
}

int main() {
    vector<vector<int>> intervals = {{1,4},{2,4},{3,6},{4,4}};
    vector<int> queries = {2,3,4,5};
    vector<int> result = minIntervalHeap(intervals, queries);
    for (int val : result) cout << val << ' ';
    cout << endl;
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[0] < b[0]; });Sort intervals by start time for sequential processing
sort(sortedQueries.begin(), sortedQueries.end());Sort queries by value while keeping original indices
while (i < (int)intervals.size() && intervals[i][0] <= q) {Add intervals starting before or at query to min-heap
while (!minHeap.empty() && minHeap.top().second < q) {Remove intervals from heap that ended before query
function minIntervalHeap(intervals, queries) {
    intervals.sort((a,b) => a[0] - b[0]);
    const sortedQueries = queries.map((q,i) => [q,i]).sort((a,b) => a[0] - b[0]);
    const res = new Array(queries.length).fill(-1);
    const minHeap = [];
    function heapPush(val) {
        minHeap.push(val);
        let i = minHeap.length - 1;
        while (i > 0) {
            let p = Math.floor((i - 1) / 2);
            if (minHeap[p][0] <= minHeap[i][0]) break;
            [minHeap[p], minHeap[i]] = [minHeap[i], minHeap[p]];
            i = p;
        }
    }
    function heapPop() {
        const top = minHeap[0];
        const last = minHeap.pop();
        if (minHeap.length > 0) {
            minHeap[0] = last;
            let i = 0;
            while (true) {
                let left = 2*i + 1, right = 2*i + 2, smallest = i;
                if (left < minHeap.length && minHeap[left][0] < minHeap[smallest][0]) smallest = left;
                if (right < minHeap.length && minHeap[right][0] < minHeap[smallest][0]) smallest = right;
                if (smallest === i) break;
                [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
                i = smallest;
            }
        }
        return top;
    }
    let i = 0;
    for (const [q, idx] of sortedQueries) {
        while (i < intervals.length && intervals[i][0] <= q) {
            const length = intervals[i][1] - intervals[i][0] + 1;
            heapPush([length, intervals[i][1]]);
            i++;
        }
        while (minHeap.length && minHeap[0][1] < q) {
            heapPop();
        }
        res[idx] = minHeap.length ? minHeap[0][0] : -1;
    }
    return res;
}

// Test
const intervals = [[1,4],[2,4],[3,6],[4,4]];
const queries = [2,3,4,5];
console.log(minIntervalHeap(intervals, queries)); // [3,3,1,4]
Line Notes
intervals.sort((a,b) => a[0] - b[0]);Sort intervals by start time for ordered processing
const sortedQueries = queries.map((q,i) => [q,i]).sort((a,b) => a[0] - b[0]);Sort queries by value while tracking original indices
while (i < intervals.length && intervals[i][0] <= q) {Add intervals starting before or at query to min-heap
while (minHeap.length && minHeap[0][1] < q) {Remove intervals from heap that ended before query
⏱
Complexity
TimeO(n log n + m log n)
SpaceO(n + m)

Sorting intervals and queries takes O(n log n + m log m). Each interval is pushed and popped at most once from the heap, so heap operations total O(n log n). Overall dominated by sorting and heap operations.

💡 For n and m around 100,000, this approach can run efficiently within seconds, unlike brute force.
Interview Verdict: Accepted

This approach is efficient and practical for large inputs, demonstrating mastery of sorting and heap data structures.

🧠
Binary Search + Preprocessing Intervals by Length
💡 This approach uses binary search on interval lengths combined with interval coverage checks to find the minimum interval length for each query. It is more advanced and useful when queries are large and intervals can be preprocessed.

Intuition

Sort intervals by length. For each query, binary search on interval lengths to find the smallest length interval that covers the query by checking coverage with prefix sums or segment trees.

Algorithm

  1. Sort intervals by their length.
  2. Build a data structure (like segment tree or prefix sums) to quickly check if any interval of a given length covers a query.
  3. For each query, binary search over interval lengths:
  4. Check if any interval of that length covers the query using the data structure.
  5. Return the smallest length found or -1 if none.
💡 This algorithm is more complex but reduces query time by trading off preprocessing and binary search.
</>
Code
from typing import List
import bisect

def min_interval_binary_search(intervals: List[List[int]], queries: List[int]) -> List[int]:
    intervals.sort(key=lambda x: x[1] - x[0] + 1)
    lengths = [end - start + 1 for start, end in intervals]
    starts = [start for start, end in intervals]
    ends = [end for start, end in intervals]

    def covers(query, length):
        # Check if any interval with length <= length covers query
        # Using binary search on intervals sorted by length
        idx = bisect.bisect_right(lengths, length)
        for i in range(idx):
            if starts[i] <= query <= ends[i]:
                return True
        return False

    res = []
    max_len = lengths[-1] if lengths else 0
    for q in queries:
        left, right = 1, max_len
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if covers(q, mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        res.append(ans)
    return res

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[2,4],[3,6],[4,4]]
    queries = [2,3,4,5]
    print(min_interval_binary_search(intervals, queries))  # Output: [3,3,1,4]
Line Notes
intervals.sort(key=lambda x: x[1] - x[0] + 1)Sort intervals by their length to enable binary search
def covers(query, length):Helper function to check if any interval of length <= given length covers query
idx = bisect.bisect_right(lengths, length)Find index of intervals with length <= current mid
while left <= right:Binary search over possible interval lengths to find minimum covering length
import java.util.*;

public class MinIntervalBinarySearch {
    public static int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1] - a[0] + 1));
        int n = intervals.length;
        int[] lengths = new int[n];
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            lengths[i] = intervals[i][1] - intervals[i][0] + 1;
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        int maxLen = n > 0 ? lengths[n - 1] : 0;
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int q = queries[i];
            int left = 1, right = maxLen, ans = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (covers(q, mid, lengths, starts, ends)) {
                    ans = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            res[i] = ans;
        }
        return res;
    }

    private static boolean covers(int query, int length, int[] lengths, int[] starts, int[] ends) {
        int idx = Arrays.binarySearch(lengths, length);
        if (idx < 0) idx = -idx - 1;
        for (int i = 0; i < idx; i++) {
            if (starts[i] <= query && query <= ends[i]) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{2,4},{3,6},{4,4}};
        int[] queries = {2,3,4,5};
        System.out.println(Arrays.toString(minInterval(intervals, queries)));
    }
}
Line Notes
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1] - a[0] + 1));Sort intervals by length for binary search
while (left <= right) {Binary search over interval lengths to find minimum covering length
int idx = Arrays.binarySearch(lengths, length);Find index of intervals with length <= mid
for (int i = 0; i < idx; i++) {Check coverage for intervals with length <= mid
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool covers(int query, int length, const vector<int>& lengths, const vector<int>& starts, const vector<int>& ends) {
    int idx = (int)(upper_bound(lengths.begin(), lengths.end(), length) - lengths.begin());
    for (int i = 0; i < idx; i++) {
        if (starts[i] <= query && query <= ends[i]) return true;
    }
    return false;
}

vector<int> minIntervalBinarySearch(vector<vector<int>>& intervals, vector<int>& queries) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
        return (a[1] - a[0]) < (b[1] - b[0]);
    });
    int n = intervals.size();
    vector<int> lengths(n), starts(n), ends(n);
    for (int i = 0; i < n; i++) {
        lengths[i] = intervals[i][1] - intervals[i][0] + 1;
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }
    int maxLen = n > 0 ? lengths.back() : 0;
    vector<int> res;
    for (int q : queries) {
        int left = 1, right = maxLen, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (covers(q, mid, lengths, starts, ends)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        res.push_back(ans);
    }
    return res;
}

int main() {
    vector<vector<int>> intervals = {{1,4},{2,4},{3,6},{4,4}};
    vector<int> queries = {2,3,4,5};
    vector<int> result = minIntervalBinarySearch(intervals, queries);
    for (int val : result) cout << val << ' ';
    cout << endl;
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {Sort intervals by length for binary search
int idx = (int)(upper_bound(lengths.begin(), lengths.end(), length) - lengths.begin());Find count of intervals with length <= mid
while (left <= right) {Binary search over interval lengths to find minimum covering length
for (int i = 0; i < idx; i++) {Check if any interval with length <= mid covers query
function minIntervalBinarySearch(intervals, queries) {
    intervals.sort((a,b) => (a[1]-a[0]) - (b[1]-b[0]));
    const lengths = intervals.map(i => i[1] - i[0] + 1);
    const starts = intervals.map(i => i[0]);
    const ends = intervals.map(i => i[1]);

    function covers(query, length) {
        let idx = upperBound(lengths, length);
        for (let i = 0; i < idx; i++) {
            if (starts[i] <= query && query <= ends[i]) return true;
        }
        return false;
    }

    function upperBound(arr, target) {
        let left = 0, right = arr.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (arr[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    const maxLen = lengths.length ? lengths[lengths.length - 1] : 0;
    const res = [];
    for (const q of queries) {
        let left = 1, right = maxLen, ans = -1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (covers(q, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        res.push(ans);
    }
    return res;
}

// Test
const intervals = [[1,4],[2,4],[3,6],[4,4]];
const queries = [2,3,4,5];
console.log(minIntervalBinarySearch(intervals, queries)); // [3,3,1,4]
Line Notes
intervals.sort((a,b) => (a[1]-a[0]) - (b[1]-b[0]));Sort intervals by length for binary search
function covers(query, length) {Check if any interval with length <= given length covers query
while (left <= right) {Binary search over interval lengths to find minimum covering length
let idx = upperBound(lengths, length);Find number of intervals with length <= mid
⏱
Complexity
TimeO(n log n + m n log n)
SpaceO(n + m)

Sorting intervals is O(n log n). For each query, binary searching over lengths is O(log n), but coverage check is O(n) in worst case, leading to O(m n log n) total.

💡 This approach is slower than the heap method for large inputs but shows a different way to think about the problem.
Interview Verdict: Accepted but less efficient

This method is correct but less practical for large inputs due to coverage checks; useful to show binary search skills.

📊
All Approaches - One-Glance Tradeoffs
💡 The heap-based sorting approach is the best balance of efficiency and implementation complexity for interviews.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n*m)O(m)NoN/AMention only - never code due to inefficiency
2. Sorting + Min-HeapO(n log n + m log n)O(n + m)NoN/ACode this approach for best performance and clarity
3. Binary Search + Coverage CheckO(n log n + m n log n)O(n + m)NoN/ADiscuss as alternative, but avoid coding due to complexity
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding each approach, and learn how to explain your thought process clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force approach to demonstrate understanding.Explain why brute force is inefficient and propose sorting + heap optimization.Implement the heap-based solution carefully.Discuss possible follow-ups and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test: 7min. Total ~30min

What the Interviewer Tests

The interviewer tests your ability to handle large inputs efficiently, use sorting and heaps, and reason about interval coverage and query processing.

Common Follow-ups

  • What if intervals are updated dynamically? → Use segment trees or balanced BSTs.
  • Can you solve with offline queries? → Yes, sorting queries and intervals helps.
💡 Follow-ups often test your knowledge of data structures for dynamic intervals and offline query processing.
🔍
Pattern Recognition

When to Use

1) You have intervals and queries; 2) Need to find minimal covering interval; 3) Queries can be processed offline; 4) Efficient interval coverage checking is required.

Signature Phrases

'smallest interval that includes the query''for each query find minimum length interval covering it'

NOT This Pattern When

Problems that only ask for interval intersections or unions without queries are different.

Similar Problems

Minimum Number of Arrows to Burst Balloons - interval coverage with greedyEmployee Free Time - merging intervals to find gapsMeeting Rooms II - scheduling intervals with heaps

Practice

(1/5)
1. Consider the following Python code implementing the min-heap approach to find the minimum number of meeting rooms. Given the input intervals = [[0,30],[5,10],[15,20]], what is the value of the heap after processing the second interval (i=1)?
easy
A. [10]
B. [30, 10]
C. [30, 20]
D. [5, 10]

Solution

  1. Step 1: Trace heap after first interval [0,30].

    Heap contains [30] after pushing end time of first meeting.
  2. Step 2: Process second interval [5,10].

    Since 5 < 30 (heap[0]), no pop occurs; push 10. Heap now contains [10, 30] (min-heap property).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Heap stores end times; after second interval, both 30 and 10 are in heap [OK]
Hint: Heap stores end times; no pop if start < earliest end [OK]
Common Mistakes:
  • Popping when start < earliest end
  • Confusing heap contents order
  • Forgetting to push current interval's end
2. Examine the following buggy code for Employee Free Time. Which line contains the subtle bug causing incorrect free time intervals?
medium
A. Line appending end event with (interval[1], -1)
B. Line appending start event with (interval[0], 1)
C. Line updating prev = time inside loop
D. Line sorting events with key=lambda x: (x[0], -x[1])

Solution

  1. Step 1: Understand sorting order impact

    End events must come before start events at same time to avoid false free intervals.
  2. Step 2: Identify bug in sorting key

    Sorting with key (x[0], -x[1]) puts start events before end events at ties, causing incorrect free time detection.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Correct sorting is (x[0], x[1]) to put end events before start [OK]
Hint: End events must sort before start events at same time [OK]
Common Mistakes:
  • Sorting start before end events at same timestamp
3. Consider this buggy code snippet for removing covered intervals:
def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], x[1]))  # Bug here
    count = 0
    max_end = 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count
What is the bug in this code?
medium
A. The condition 'if end > max_end' should be 'if end >= max_end' to include equal ends.
B. max_end is not updated correctly inside the loop.
C. Sorting by end ascending instead of descending causes coverage detection failure.
D. The nested loop for coverage check is missing, causing incorrect results.

Solution

  1. Step 1: Analyze sorting key

    Sorting by (start ascending, end ascending) orders intervals with same start from shortest to longest, which breaks coverage detection.
  2. Step 2: Understand coverage detection logic

    Coverage detection relies on intervals with same start being sorted longest first (end descending) so covered intervals come after.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting end ascending causes missed coverage when starts equal [OK]
Hint: Sort end descending to detect coverage correctly [OK]
Common Mistakes:
  • Sorting end ascending instead of descending
  • Using strict inequality incorrectly
4. Suppose the meeting intervals can be reused multiple times (i.e., a meeting can be attended multiple times if no overlaps occur). Which modification to the algorithm is necessary to correctly determine if a person can attend all meetings without overlap?
hard
A. Sort intervals by end time and greedily select intervals to maximize non-overlapping meetings.
B. No change needed; the original algorithm already handles reuse correctly.
C. Use a frequency map to count how many times each interval appears and check overlaps accordingly.
D. Sort intervals by start time and check overlaps as before, but also track counts of repeated intervals.

Solution

  1. Step 1: Understand reuse scenario

    Reusing intervals means attending multiple instances of the same meeting, so we want to maximize the number of non-overlapping meetings.
  2. Step 2: Identify correct approach

    Sorting by end time and greedily selecting earliest finishing meetings maximizes non-overlapping intervals, handling reuse correctly.
  3. Step 3: Why other options fail

    Original algorithm only checks if all intervals can be attended once; frequency maps or tracking counts do not solve scheduling conflicts optimally.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Greedy by end time is classic interval scheduling for maximum non-overlapping intervals [OK]
Hint: Reuse requires interval scheduling by end time [OK]
Common Mistakes:
  • Assuming original overlap check suffices for reuse
  • Trying to track counts without scheduling logic
5. Suppose intervals can be reused multiple times (i.e., you can merge overlapping intervals repeatedly, possibly reusing intervals). Which modification to the merge intervals algorithm correctly handles this scenario?
hard
A. Use the same sorting + one pass merge approach; repeated intervals will be merged naturally.
B. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes.
C. Use a brute force nested loop approach to merge intervals until no overlaps remain.
D. Use a graph-based approach to find connected components of overlapping intervals and merge each component.

Solution

  1. Step 1: Understand that reusing intervals means overlaps can form complex connected groups.

    Simple one-pass merge assumes intervals appear once and sorted order suffices.
  2. Step 2: Recognize that overlapping intervals form connected components in a graph.

    Building a graph where intervals are nodes and edges represent overlaps allows merging all connected intervals correctly.
  3. Step 3: Evaluate options.

    Use the same sorting + one pass merge approach; repeated intervals will be merged naturally. fails because one pass merge assumes no reuse. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes. is inefficient and may not terminate quickly. Use a brute force nested loop approach to merge intervals until no overlaps remain. is brute force and inefficient. Use a graph-based approach to find connected components of overlapping intervals and merge each component. correctly models the problem and merges all connected intervals.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Graph connected components capture all overlapping intervals including reuse. [OK]
Hint: Model reuse as graph connected components [OK]
Common Mistakes:
  • Assuming one pass merge works with reuse
  • Using repeated merges without termination guarantee
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard