350. Minimum Interval to Include Each Query

HardHeap

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.

Examples

Input: [[1,4],[2,4],[3,6],[4,4]] [2,3,4,5]

Output: [3,3,1,4]

Explanation: Query 4 is covered by [4,4] (size 1); query 5 only by [3,6] (size 4).

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
Loading...

Run checks all cases above. Submit evaluates all test cases.