Minimum Interval to Include Each Query

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m)	O(m)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Min-Heap	O(n log n + m log n)	O(n + m)	No	N/A	Code this approach for best performance and clarity
3. Binary Search + Coverage Check	O(n log n + m n log n)	O(n + m)	No	N/A	Discuss 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. Consider the following Python code that determines if a person can attend all meetings given a list of intervals. What is the return value when the input is [[7,10],[2,4]]?

from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    end = float('-inf')
    for interval in intervals:
        if interval[0] < end:
            return False
        end = interval[1]
    return True

print(can_attend_meetings([[7,10],[2,4]]))

easy

A. None

B. False

C. Raises an exception

D. True

Solution

1. Step 1: Sort intervals by start time

   Input [[7,10],[2,4]] becomes [[2,4],[7,10]].

2. Step 2: Iterate and check overlaps

   Initialize end = -inf. First interval start=2 > -inf, update end=4. Second interval start=7 > 4, update end=10. No overlaps found, return True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Intervals sorted and no overlaps detected [OK]

Hint: Sort then check if current start < previous end [OK]

Common Mistakes:

• Confusing return value due to unsorted intervals

2. You are given a list of intervals where each interval has a start and end time. Your goal is to select the maximum number of intervals such that none of the selected intervals overlap. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming that tries all subsets of intervals to find the maximum non-overlapping set.

B. Sort intervals by their start time and always pick the earliest starting interval first.

C. Sort intervals by their end time and greedily select intervals that start after the last selected interval ends.

D. Use a graph coloring algorithm to assign intervals to different colors ensuring no overlaps.

Solution

1. Step 1: Understand the problem goal

   The problem requires selecting the maximum number of intervals with no overlaps.

2. Step 2: Identify the optimal greedy strategy

   Sorting intervals by their end time and greedily picking intervals that start after the last selected interval ends ensures the maximum number of intervals are chosen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy by earliest end time is a classic optimal approach [OK]

Hint: Sort by end time for max non-overlapping intervals [OK]

Common Mistakes:

• Sorting by start time and picking earliest start first
• Trying brute force DP without pruning
• Using graph coloring which is unrelated here

3. Examine the following buggy code for the Meeting Rooms II problem. Which line contains the subtle bug that can cause incorrect room count?

medium

A. Line 3: Missing check for empty intervals list.

B. Line 9: Incorrect condition using >= instead of > for overlap.

C. Line 11: Using heappush without popping first.

D. Line 6: Intervals are not sorted before processing.

Solution

1. Step 1: Identify missing sorting.

   Intervals must be sorted by start time before heap processing; missing this breaks heap logic.

2. Step 2: Confirm other lines.

   Empty check is present; condition >= is correct for allowing room reuse; pushing after popping is correct.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without sorting, heap logic fails to track earliest ending meeting [OK]

Hint: Heap logic requires sorted intervals by start time [OK]

Common Mistakes:

• Confusing overlap condition with <=
• Forgetting to sort intervals
• Misordering heap push/pop

4. What is the time complexity of the optimal greedy algorithm that sorts balloons by their end coordinate and then iterates once to find the minimum number of arrows?

medium

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Sorting n intervals by end coordinate takes O(n log n) time.

2. Step 2: Identify iteration cost

   Single pass through sorted intervals is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Dominant cost is sorting, so total is O(n log n) [OK]

Hint: Sorting dominates; iteration is linear [OK]

Common Mistakes:

• Assuming linear time because of single pass
• Confusing with brute force O(n^2)
• Ignoring sorting cost

5. Suppose intervals can be reused multiple times (i.e., you can select the same interval multiple times if it does not overlap with itself). Which modification to the greedy algorithm is correct to find the maximum number of non-overlapping intervals under this new condition?

hard

A. Sort intervals by end time and greedily select intervals, resetting last_end after each selection to allow reuse.

B. Use dynamic programming to consider multiple selections of intervals, since greedy no longer works.

C. Sort intervals by start time and greedily select intervals without updating last_end to allow reuse.

D. Sort intervals by end time and greedily select intervals, but allow intervals to be selected multiple times by not updating last_end.

Solution

1. Step 1: Understand reuse changes problem

   Allowing reuse means intervals can be selected multiple times, breaking the greedy assumption of one-time selection.

2. Step 2: Identify correct approach

   Dynamic programming is needed to explore multiple selections and ensure maximum count without overlap.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Greedy fails with reuse; DP handles multiple selections [OK]

Hint: Reuse breaks greedy; DP needed for multiple selections [OK]

Common Mistakes:

• Trying to reuse intervals by resetting last_end incorrectly
• Ignoring overlap constraints when reusing intervals
• Assuming greedy still works unchanged