首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >区间上的动态规划

问区间上的动态规划
EN

Stack Overflow用户
提问于 2020-03-09 12:13:59
回答 1查看 144关注 0票数 2

您将获得一个连续间隔数组,即{ [a,b],[b,c],[c,d],...,[g,h],[h,i] }

给定一个n m k类型的查询,我们需要输出包含k的n,m (inclusive, 1-based indexing)之间的间隔数。

我的方法:(天真地检查n,m和keeping a counter之间的所有间隔。)

如果m-n和查询数很小,则此方法有效,但对于较大的n,m值和多个查询而言,此方法的效率非常低。

但是,如果数组中给定的间隔太大,这也会失败,因为构建dp数组需要更长的时间。

我如何解决这个问题,或者有没有一种我缺少的更简单的方法?

任何提示都会有帮助。

示例:

数组:{ [1,3],[3,2],[2,1],[1,5],[5,3] }

查询:{ 1 2 2 }、{ 1 3 3 }、{ 2 2 4 }

输出:{ 2 }、{ 2 }、{ 0 }

EN

回答 1

Stack Overflow用户

发布于 2020-03-09 15:47:03

我会用下面的方法解决这个问题。

首先,我将介绍表单的另一个数据结构数组:

代码语言:javascript
复制
[(ai,bi,ci)]

哪里

代码语言:javascript
复制
ai - interval start
bi - interval end
ci - count of intervals of original sequence hitting interval [ai,bi]

ai < bi
a(i+1) = bi

因此,这种新的数据结构覆盖了原始结构的整个范围,它正在增加,并且具有原始区间的期望计数。

现在,要找到计数,我们只需要k并执行某种二进制搜索来找到间隔。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/60594643

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档