最小ヒープで点を含む最も短い区間を答える

from heapq import heappush
from heapq import heappop


def smallest_interval(ranges, points):
    items = sorted(ranges)
    order = sorted(
        range(len(points)),
        key=lambda k: points[k],
    )
    out = [-1] * len(points)
    heap = []
    i = 0
    for k in order:
        x = points[k]
        while (
            i < len(items)
            and items[i][0] <= x
        ):
            lo, hi = items[i]
            heappush(
                heap, (hi - lo + 1, hi)
            )
            i += 1
        while heap and heap[0][1] < x:
            heappop(heap)
        if heap:
            out[k] = heap[0][0]
    return out

function smallestInterval(
  ranges, points
) {
  const items = [...ranges];
  items.sort(
    (p, q) => p[0] - q[0],
  );
  const order = points.map(
    (_, k) => k,
  );
  order.sort(
    (a, b) => points[a] - points[b],
  );
  const out = points.map(() => -1);
  const h = [];
  let i = 0;
  for (const k of order) {
    const x = points[k];
    while (
      i < items.length &&
      items[i][0] <= x
    ) {
      const [lo, hi] = items[i];
      push(h, [hi - lo + 1, hi]);
      i++;
    }
    while (
      h.length > 0 && h[0][1] < x
    ) {
      pop(h);
    }
    if (h.length > 0) {
      out[k] = h[0][0];
    }
  }
  return out;
}

function less(a, b) {
  if (a[0] !== b[0]) {
    return a[0] < b[0];
  }
  return a[1] < b[1];
}

function push(h, x) {
  h.push(x);
  let i = h.length - 1;
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (!less(h[i], h[p])) {
      return;
    }
    [h[p], h[i]] = [h[i], h[p]];
    i = p;
  }
}

function pop(h) {
  const top = h[0];
  const last = h.pop();
  const n = h.length;
  if (n === 0) {
    return top;
  }
  h[0] = last;
  const lt = (a, b) =>
    less(h[a], h[b]);
  let i = 0;
  while (true) {
    let s = i;
    const l = 2 * i + 1;
    const r = l + 1;
    if (l < n && lt(l, s)) {
      s = l;
    }
    if (r < n && lt(r, s)) {
      s = r;
    }
    if (s === i) {
      return top;
    }
    [h[s], h[i]] = [h[i], h[s]];
    i = s;
  }
}

import (
	"container/heap"
	"slices"
)

type span struct {
	size, hi int
}

type spans []span

func (h spans) Len() int {
	return len(h)
}

func (h spans) Less(
	i, j int,
) bool {
	if h[i].size != h[j].size {
		return h[i].size < h[j].size
	}
	return h[i].hi < h[j].hi
}

func (h spans) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *spans) Push(x any) {
	*h = append(*h, x.(span))
}

func (h *spans) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func smallestInterval(
	ranges [][]int, points []int,
) []int {
	items := slices.Clone(ranges)
	slices.SortFunc(items, func(
		p, q []int,
	) int {
		return p[0] - q[0]
	})
	n := len(points)
	order := make([]int, n)
	for k := range order {
		order[k] = k
	}
	slices.SortFunc(order, func(
		a, b int,
	) int {
		return points[a] - points[b]
	})
	out := make([]int, n)
	h := &spans{}
	i := 0
	for _, k := range order {
		x := points[k]
		for i < len(items) &&
			items[i][0] <= x {
			lo, hi := items[i][0],
				items[i][1]
			heap.Push(h,
				span{hi - lo + 1, hi})
			i++
		}
		for h.Len() > 0 &&
			(*h)[0].hi < x {
			heap.Pop(h)
		}
		out[k] = -1
		if h.Len() > 0 {
			out[k] = (*h)[0].size
		}
	}
	return out
}