包含每个查询的最小区间

1851. 包含每个查询的最小区间

给你一个二维整数数组 intervals ，其中 intervals[i] = [left_i, right_i] 表示第 i 个区间开始于 left_i 、结束于 right_i（包含两侧取值，闭区间）。区间的长度定义为区间中包含的整数数目，更正式地表达是 right_i - left_i + 1 。

再给你一个整数数组 queries 。第 j 个查询的答案是满足 left_i <= queries[j] <= right_i 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。

以数组形式返回对应查询的所有答案。

示例 1：

输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
输出：[3,3,1,4]
解释：查询处理如下：
- Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
- Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。

示例 2：

输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
输出：[2,-1,4,6]
解释：查询处理如下：
- Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。
- Query = 19：不存在包含 19 的区间，答案为 -1 。
- Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。
- Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。

提示：

1 <= intervals.length <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
1 <= left_i <= right_i <= 10⁷
1 <= queries[j] <= 10⁷

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) { } };

java 解法, 执行用时: 109 ms, 内存消耗: 93 MB, 提交时间: 2023-07-18 09:16:13

// 优先队列
class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        //将区间按区间头从小到大排序
        Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));
        //记录queries以及i，也就是queries[i]和i
        int[][] que = new int[queries.length][2];
        for(int i = 0; i < queries.length; ++i) {
            que[i][0] = queries[i];
            que[i][1] = i;
        }
        //将值排序，小的在前
        Arrays.sort(que, (o1, o2) -> (o1[0] - o2[0]));
        int[] res = new int[queries.length];
        Arrays.fill(res, -1);
        //优先级队列，区间长度小的区间优先，在队列头
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> (o1[1] - o1[0] - o2[1] + o2[0]));
        //记录第几个区间，因为intervals和queries都是排好序的，所以用index记录目前走到哪里了
        int index = 0;
        for(int i = 0; i < queries.length; ++i) {
            //先把区间左边界小于等于queries[i]的区间加进去
            while(index < intervals.length && que[i][0] >= intervals[index][0]) {
                queue.offer(new int[]{intervals[index][0], intervals[index][1]});
                index += 1;
            }
            //再把区间右边界小于queries[i]的区间删除
            while(!queue.isEmpty() && queue.peek()[1] < que[i][0]) {
                queue.poll();
            }
            /*
            为什么不需要动index？
            正如上面的注释，intervals和queries都是排好序的
            如果这个区间不合适被删除了，是因为这个区间是在queries[i]的左面，但是之后的queries[i + 1]都比queries[i]大
            所以这个区间在以后肯定也不合适，就删除了，不再要了
            */
            if(!queue.isEmpty()) {
                int[] t = queue.peek();
                res[que[i][1]] = t[1] - t[0] + 1;  
            }
        }
        return res;

    }
}

cpp 解法, 执行用时: 500 ms, 内存消耗: 106.6 MB, 提交时间: 2023-07-18 09:14:50

class Solution {
public:
  vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
    // 按照区间长度从小到大排序
    sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
      return a[1] - a[0] < b[1] - b[0];
    });

    // 离线：按查询位置排序
    int m = queries.size();
    vector<int> ids(m);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) { return queries[i] < queries[j]; });

    // 并查集
    vector<int> fa(m + 1);
    iota(fa.begin(), fa.end(), 0);
    function<int(int)> find = [&](int x) -> int {
      return x == fa[x] ? x : fa[x] = find(fa[x]);
    };

    // 对于每个区间，回答 [left, right] 内的询问
    vector<int> ans(m, -1);
    for (const auto& p : intervals) {
      int left = p[0];
      int right = p[1];
      int len = right - left + 1;
      // 二分查找大于等于区间左端点的最小询问
      auto pos = lower_bound(ids.begin(), ids.end(), left,
                             [&](int id, int value) { return queries[id] < value; }) - ids.begin();
      // 回答所有在区间 [left, right] 还没被回答过的询问
      for (int i = find(pos); i < m && queries[ids[i]] <= right; i = find(i + 1)) {
        ans[ids[i]] = len;
        fa[i] = i + 1;  // 查询之后，将其指向下一个询问
      }
    }
    return ans;
  }
};

java 解法, 执行用时: 165 ms, 内存消耗: 94.8 MB, 提交时间: 2023-07-18 09:14:18

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        // 按照区间长度由小到大排序，这样每次回答的时候用的就是长度最小的区间
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[1] - o[0]));

        int m = queries.length;
        // pos, i
        int[][] qs = new int[m][2];
        for (int i = 0; i < m; i++) {
            qs[i] = new int[]{queries[i], i};
        }
        // 离线：按查询位置排序
        Arrays.sort(qs, Comparator.comparingInt(o -> o[0]));

        DSU dsu = new DSU(m + 1);
        int[] ans = new int[m];
        Arrays.fill(ans, -1);
        for (int[] interval : intervals) {
            int l = interval[0], r = interval[1];

            // 二分找大于等于区间左端点的最小询问
            int left = 0;
            int right = m;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (qs[mid][0] >= l) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }

            for (int i = dsu.find(left); i < m && qs[i][0] <= r; i = dsu.find(i + 1)) {
                ans[qs[i][1]] = r - l + 1;
                dsu.fa[i] = i + 1;
            }
        }
        return ans;
    }

    // 并查集
    private static class DSU {
        int[] fa;

        public DSU(int n) {
            fa = new int[n];
            for (int i = 0; i < n; i++) {
                fa[i] = i;
            }
        }

        int find(int x) {
            if (x != fa[x]) {
                fa[x] = find(fa[x]);
            }
            return fa[x];
        }
    }
}

python3 解法, 执行用时: 516 ms, 内存消耗: 59.9 MB, 提交时间: 2023-07-18 09:13:24

# 离线查询 + 优先队列
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        import heapq
        m, n = len(intervals), len(queries)
        ans = [-1] * n

        intervals.sort()
        nums = sorted([(q, i) for i, q in enumerate(queries)])
        h = []
        idx = 0

        for q, i in nums:
            while idx < m and q >= intervals[idx][0]:
                l, r = intervals[idx]
                heapq.heappush(h, (r - l + 1, l, r))
                idx += 1

            while h and q > h[0][2]:
                heapq.heappop(h)

            if h:
                ans[i] = h[0][0]

        return ans

python3 解法, 执行用时: 604 ms, 内存消耗: 61 MB, 提交时间: 2023-07-18 09:12:11

# 排序 + 并查集
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        m, n = len(intervals), len(queries)

        intervals.sort(key=lambda x: x[1] - x[0])
        queries = sorted([(q, i) for i, q in enumerate(queries)])

        fa = list(range(n + 1))

        def find(x):
            if x != fa[x]:
                fa[x] = find(fa[x])
            return fa[x]

        ans = [-1] * n

        for l, r in intervals:
            length = r - l + 1
            pos = bisect_left(queries, (l, -1))

            idx = find(pos)
            while idx < n and queries[idx][0] <= r:
                ans[queries[idx][1]] = length
                fa[idx] = idx + 1
                idx = find(idx + 1)

        return ans

golang 解法, 执行用时: 368 ms, 内存消耗: 23 MB, 提交时间: 2023-07-18 09:10:28

// 按区间长度排序 + 离线询问 + 并查集
func minInterval(intervals [][]int, queries []int) []int {
	// 按照区间长度由小到大排序，这样每次回答的时候用的就是长度最小的区间
	sort.Slice(intervals, func(i, j int) bool { a, b := intervals[i], intervals[j]; return a[1]-a[0] < b[1]-b[0] })

	m := len(queries)
	type pair struct{ pos, i int }
	qs := make([]pair, m)
	for i, q := range queries {
		qs[i] = pair{q, i}
	}
	// 离线：按查询位置排序
	sort.Slice(qs, func(i, j int) bool { return qs[i].pos < qs[j].pos })

	// 初始化并查集
	fa := make([]int, m+1)
	for i := range fa {
		fa[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if fa[x] != x {
			fa[x] = find(fa[x])
		}
		return fa[x]
	}

	ans := make([]int, m)
	for i := range ans {
		ans[i] = -1
	}
	// 对每个区间，回答所有在 [l,r] 范围内的询问
	// 由于每次回答询问之后，都将其指向了下一个询问
	// 所以若 i = find(i) 符合 i < m && qs[i].pos <= r 的条件，则必然是一个在 [l,r] 范围内的还没有回答过的询问
	for _, p := range intervals {
		l, r := p[0], p[1]
		length := r - l + 1
		// 二分找大于等于区间左端点的最小询问
		i := sort.Search(m, func(i int) bool { return qs[i].pos >= l })
		// 回答所有询问位置在 [l,r] 范围内的还没有被回答过的询问
		for i = find(i); i < m && qs[i].pos <= r; i = find(i + 1) {
			ans[qs[i].i] = length
			fa[i] = i + 1
		}
	}
	return ans
}

上一题

下一题

详情