Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1851.html

1851. Minimum Interval to Include Each Query

Level

Medium

Description

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i-th interval starting at left_i and ending at right_i (inclusive). The size of an interval is defined as the number of integers it contains, or more formally right_i - left_i + 1.

You are also given an integer array queries. The answer to the j-th query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]

Output: [3,3,1,4]

Explanation: The queries are processed as follows:

  • Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
  • Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
  • Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
  • Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]

Output: [2,-1,4,6]

Explanation: The queries are processed as follows:

  • Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
  • Query = 19: None of the intervals contain 19. The answer is -1.
  • Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
  • Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

  • 1 <= intervals.length <= 10^5
  • 1 <= queries.length <= 10^5
  • intervals[i].length == 2
  • 1 <= left_i <= right_i <= 10^7
  • 1 <= queries[j] <= 10^7

Solution

Use a tree map to store the query results, and use a tree set to store the queries that do not have results yet. Initially, put all the elements in queries into the tree set. Sort intervals according to the intervals’ sizes.

Loop over intervals. For each interval, obtain the start and the end of the interval and calculate the size of the interval. For all the elements in the tree set that are in the range [start, end], these queries’ results are the size of the current interval, so put the query results into the tree map and remove these queries from the tree set.

Finally, create an array to store the queries’ results and return the array.

  • class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int query : queries)
            set.add(query);
        int intervalsCount = intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                int length1 = interval1[1] - interval1[0] + 1, length2 = interval2[1] - interval2[0] + 1;
                if (length1 != length2)
                    return length1 - length2;
                else
                    return interval1[0] - interval2[0];
            }
        });
        for (int i = 0; i < intervalsCount; i++) {
            int[] interval = intervals[i];
            int start = interval[0], end = interval[1];
            int size = end - start + 1;
            Set<Integer> subSet = new HashSet<Integer>(set.subSet(start, true, end, true));
            for (int num : subSet) {
                map.put(num, size);
                set.remove(num);
            }
        }
        int queriesCount = queries.length;
        int[] answers = new int[queriesCount];
        for (int i = 0; i < queriesCount; i++)
            answers[i] = map.getOrDefault(queries[i], -1);
        return answers;
    }
}

  • # 1851. Minimum Interval to Include Each Query
# https://leetcode.com/problems/minimum-interval-to-include-each-query/

class Solution:
    def minInterval(self, A, queries):
        A = sorted(A)[::-1]
        h = []
        res = {}

        for q in sorted(queries):
            while A and A[-1][0] <= q:
                i, j = A.pop()
                if j >= q:
                    heapq.heappush(h, [j - i + 1, j])
            while h and h[0][1] < q:
                heapq.heappop(h)
            res[q] = h[0][0] if h else -1

        return [res[q] for q in queries]
        


  • class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        int n = intervals.size(), m = queries.size();
        sort(intervals.begin(), intervals.end());
        using pii = pair<int, int>;
        vector<pii> qs;
        for (int i = 0; i < m; ++i) {
            qs.emplace_back(queries[i], i);
        }
        sort(qs.begin(), qs.end());
        vector<int> ans(m, -1);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        int i = 0;
        for (auto& [x, j] : qs) {
            while (i < n && intervals[i][0] <= x) {
                int a = intervals[i][0], b = intervals[i][1];
                pq.emplace(b - a + 1, b);
                ++i;
            }
            while (!pq.empty() && pq.top().second < x) {
                pq.pop();
            }
            if (!pq.empty()) {
                ans[j] = pq.top().first;
            }
        }
        return ans;
    }
};

  • func minInterval(intervals [][]int, queries []int) []int {
	n, m := len(intervals), len(queries)
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	qs := make([][2]int, m)
	ans := make([]int, m)
	for i := range qs {
		qs[i] = [2]int{queries[i], i}
		ans[i] = -1
	}
	sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
	pq := hp{}
	i := 0
	for _, q := range qs {
		x, j := q[0], q[1]
		for i < n && intervals[i][0] <= x {
			a, b := intervals[i][0], intervals[i][1]
			heap.Push(&pq, pair{b - a + 1, b})
			i++
		}
		for len(pq) > 0 && pq[0].r < x {
			heap.Pop(&pq)
		}
		if len(pq) > 0 {
			ans[j] = pq[0].v
		}
	}
	return ans
}

type pair struct{ v, r int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

All Problems

All Solutions