# 1851. Minimum Interval to Include Each Query

```
T: o(nlogn + qlogq)
S: O(n + q)
```

````java
```java
class Solution {

    public int[] minInterval(int[][] intervals, int[] queries) {
        PriorityQueue<Integer[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // < n
        Map<Integer, Integer> res = new HashMap<>(); //q
        int[] clonedQ = queries.clone();
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // nlogn
        Arrays.sort(clonedQ); // qlogq

        int index = 0;
        for (int q : clonedQ) {    
            while (index < n && intervals[index][0] <= q) {
                int r = intervals[index][1];
                int l = intervals[index][0];
                pq.offer(new Integer[] {r - l + 1, r});
                index++;
            }
            while (!pq.isEmpty() && pq.peek()[1] < q) {
                pq.poll();
            }
            res.put(q, pq.isEmpty() ? -1 : pq.peek()[0]);
        }
        int i = 0;
        int[] res2 = new int[queries.length];
        for (int q : queries) {
            res2[i++] = res.get(q);
        }
        return res2;
    }
}

/*
[[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]

find left <= q

then find right >= q
use treemap or pq <duration, right>
if right < q -> pop 
else pq first is the ans
*/
```
````
