#include <stdlib.h>
typedef struct {
int size, end; // heap ordered by size, then end
} Entry;
static int **sortedIntervals;
static int *sortedQueries;
static int cmpInterval(const void *a, const void *b) {
const int *x = *(int *const *)a, *y = *(int *const *)b;
return (x[0] > y[0]) - (x[0] < y[0]);
}
static int cmpQueryIdx(const void *a, const void *b) {
int x = sortedQueries[*(const int *)a], y = sortedQueries[*(const int *)b];
return (x > y) - (x < y);
}
static int less(Entry a, Entry b) {
return a.size < b.size || (a.size == b.size && a.end < b.end);
}
static void push(Entry *heap, int *len, Entry e) {
int i = (*len)++;
while (i > 0 && less(e, heap[(i - 1) / 2])) {
heap[i] = heap[(i - 1) / 2];
i = (i - 1) / 2;
}
heap[i] = e;
}
static void pop(Entry *heap, int *len) {
Entry last = heap[--(*len)];
int i = 0;
for (;;) {
int child = 2 * i + 1;
if (child >= *len)
break;
if (child + 1 < *len && less(heap[child + 1], heap[child]))
child++;
if (!less(heap[child], last))
break;
heap[i] = heap[child];
i = child;
}
heap[i] = last;
}
int *minInterval(int **intervals, int intervalsSize, int *intervalsColSize,
int *queries, int queriesSize, int *returnSize) {
(void)intervalsColSize; // always 2
sortedIntervals = intervals;
sortedQueries = queries;
int *result = malloc(queriesSize * sizeof(int));
int *idx = malloc(queriesSize * sizeof(int));
Entry *heap = malloc((intervalsSize ? intervalsSize : 1) * sizeof(Entry));
int len = 0;
qsort(intervals, intervalsSize, sizeof(int *), cmpInterval);
for (int k = 0; k < queriesSize; k++)
idx[k] = k;
qsort(idx, queriesSize, sizeof(int), cmpQueryIdx);
int i = 0;
for (int k = 0; k < queriesSize; k++) {
int j = idx[k], q = queries[j];
while (i < intervalsSize && intervals[i][0] <= q) {
Entry e = {intervals[i][1] - intervals[i][0] + 1, intervals[i][1]};
push(heap, &len, e);
i++;
}
while (len > 0 && heap[0].end < q)
pop(heap, &len);
result[j] = len == 0 ? -1 : heap[0].size;
}
free(idx);
free(heap);
*returnSize = queriesSize;
return result;
}
#include <algorithm>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> minInterval(vector<vector<int>> &intervals,
vector<int> &queries) {
vector<int> result(queries.size());
vector<int> idx(queries.size());
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
sort(intervals.begin(), intervals.end());
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(),
[&](int a, int b) { return queries[a] < queries[b]; });
int i = 0, n = intervals.size();
for (int j : idx) {
int q = queries[j];
while (i < n && intervals[i][0] <= q) {
minHeap.push({intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
i++;
}
while (!minHeap.empty() && minHeap.top().second < q)
minHeap.pop();
if (minHeap.empty())
result[j] = -1;
else
result[j] = minHeap.top().first;
}
return result;
}
};
package intervals
import (
"container/heap"
"sort"
)
type entry struct{ size, end int }
type minHeap []entry
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool {
return h[i].size < h[j].size || (h[i].size == h[j].size && h[i].end < h[j].end)
}
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any) { *h = append(*h, x.(entry)) }
func (h *minHeap) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func minInterval(intervals [][]int, queries []int) []int {
result := make([]int, len(queries))
idx := make([]int, len(queries))
for k := range idx {
idx[k] = k
}
sort.Slice(intervals, func(a, b int) bool { return intervals[a][0] < intervals[b][0] })
sort.Slice(idx, func(a, b int) bool { return queries[idx[a]] < queries[idx[b]] })
h := &minHeap{}
i, n := 0, len(intervals)
for _, j := range idx {
q := queries[j]
for i < n && intervals[i][0] <= q {
heap.Push(h, entry{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]})
i++
}
for h.Len() > 0 && (*h)[0].end < q {
heap.Pop(h)
}
if h.Len() == 0 {
result[j] = -1
} else {
result[j] = (*h)[0].size
}
}
return result
}
import java.util.Arrays;
import java.util.PriorityQueue;
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
int[] result = new int[queries.length];
Integer[] idx = new Integer[queries.length];
for (int k = 0; k < idx.length; k++)
idx[k] = k;
// {size, end}, ordered by size then end
PriorityQueue<int[]> minHeap = new PriorityQueue<>(
(a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
Arrays.sort(idx, (a, b) -> Integer.compare(queries[a], queries[b]));
int i = 0, n = intervals.length;
for (int j : idx) {
int q = queries[j];
while (i < n && intervals[i][0] <= q) {
minHeap.add(new int[] { intervals[i][1] - intervals[i][0] + 1, intervals[i][1] });
i++;
}
while (!minHeap.isEmpty() && minHeap.peek()[1] < q)
minHeap.poll();
result[j] = minHeap.isEmpty() ? -1 : minHeap.peek()[0];
}
return result;
}
}
/**
* @param {number[][]} intervals
* @param {number[]} queries
* @return {number[]}
*/
var minInterval = function (intervals, queries) {
const result = new Array(queries.length);
const idx = queries.map((_, k) => k);
const heap = new MinHeap((a, b) => a[0] - b[0] || a[1] - b[1]); // [size, end]
intervals.sort((a, b) => a[0] - b[0]);
idx.sort((a, b) => queries[a] - queries[b]);
let i = 0;
const n = intervals.length;
for (const j of idx) {
const q = queries[j];
while (i < n && intervals[i][0] <= q) {
heap.push([intervals[i][1] - intervals[i][0] + 1, intervals[i][1]]);
i++;
}
while (heap.size() && heap.peek()[1] < q) heap.pop();
result[j] = heap.size() ? heap.peek()[0] : -1;
}
return result;
};
// JS has no built-in heap
class MinHeap {
constructor(cmp) {
this.a = [];
this.cmp = cmp;
}
size() {
return this.a.length;
}
peek() {
return this.a[0];
}
push(x) {
const a = this.a;
a.push(x);
for (let i = a.length - 1; i > 0; ) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0];
const last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ; ) {
let c = 2 * i + 1;
if (c >= a.length) break;
if (c + 1 < a.length && this.cmp(a[c + 1], a[c]) < 0) c++;
if (this.cmp(a[c], a[i]) >= 0) break;
[a[i], a[c]] = [a[c], a[i]];
i = c;
}
}
return top;
}
}
import heapq
from typing import List
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
result = [0] * len(queries)
min_heap = [] # (size, end)
intervals.sort()
idx = sorted(range(len(queries)), key=lambda k: queries[k])
i, n = 0, len(intervals)
for j in idx:
q = queries[j]
while i < n and intervals[i][0] <= q:
left, right = intervals[i]
heapq.heappush(min_heap, (right - left + 1, right))
i += 1
while min_heap and min_heap[0][1] < q:
heapq.heappop(min_heap)
result[j] = min_heap[0][0] if min_heap else -1
return result
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
pub fn min_interval(mut intervals: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
let mut result = vec![0; queries.len()];
let mut idx: Vec<usize> = (0..queries.len()).collect();
let mut min_heap = BinaryHeap::new(); // Reverse((size, end))
intervals.sort();
idx.sort_by_key(|&k| queries[k]);
let mut i = 0;
for j in idx {
let q = queries[j];
while i < intervals.len() && intervals[i][0] <= q {
let (left, right) = (intervals[i][0], intervals[i][1]);
min_heap.push(Reverse((right - left + 1, right)));
i += 1;
}
while let Some(&Reverse((_, end))) = min_heap.peek() {
if end >= q {
break;
}
min_heap.pop();
}
result[j] = min_heap.peek().map_or(-1, |&Reverse((size, _))| size);
}
result
}
}