202-7-18
1851. 包含每个查询的最小区间 困难
给你一个二维整数数组 intervals
,其中 intervals[i] = [lefti, righti]
表示第 i
个区间开始于 lefti
、结束于 righti
(包含两侧取值,闭区间)。区间的 长度 定义为区间中包含的整数数目,更正式地表达是 righti - lefti + 1
。
再给你一个整数数组 queries
。第 j
个查询的答案是满足 lefti <= queries[j] <= righti
的 长度最小区间 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 <= 105
1 <= queries.length <= 105
intervals[i].length == 2
1 <= lefti <= righti <= 107
1 <= queries[j] <= 107
pair {pos, i int}
来记录,其中pos就是这个元素的值,i是它在原query数组里的下标
由于我们对query
也排序过了,那么就可以使用二分查找的方法,寻找第一个>=当前区间左端点l
的下标pos
,如果这个pos
也<=r
,那么就是符合要求的,可以直接写入length
否则就查询下一个元素。还有一个问题就是,很多元素可能已经查询过了,可以使用并查集,如果该元素已经查询过了,则将它指向它的下一个元素,同样也提高了查询效率(灵神的思路是真强啊
代码
func minInterval(intervals [][]int, queries []int) []int {
//先对所有interval从小到大排序
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)
//i记录原来的位置,用于按顺序返回,pos就是查询的值,也即在坐标轴上的pos
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 x != fa[x] {
fa[x] = find(fa[x])
}
return fa[x]
}
res := make([]int ,m)
for i := range res {
res[i] = -1
}
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 })
for i = find(i); i < m && qs[i].pos <= r; i = find(i+1) {
res[qs[i].i] = length
fa[i] = i + 1
}
}
return res
}
标签:int,18,每日,pos,查询,intervals,区间,Query,一题
From: https://www.cnblogs.com/Mcyk/p/17562545.html