如何找到所有重叠区间的总和权重？

文章/答案/技术大牛

发布

2回答

algorithm

=>为我们提供了一个找到所有重叠区间的解决方案。在这个问题之上，假设每个间隔都有一个权重。当插入一个新的区间时，我的目标是找到那些重叠的区间和权重。条件:新插入的区间的结束值总是大于先前插入的区间的结束点，这将导致我们已经有了排序<e

浏览 3提问于2017-02-08得票数 1

回答已采纳

6回答

求重叠区间序列中最大和的算法

algorithm、sum、max、intervals

我正在尝试解决的问题在数字行上有一个区间列表，每个区间都有一个预先定义的分数。我需要返回可能的最大总分。 10-15 - 12 25-30 - 25 这里，间隔0-5、4-9和8-21重叠间隔10-

浏览 3提问于2010-07-14得票数 27

回答已采纳

3回答

查找pt所在的线段数

algorithm

我想找到pt所在的线段，线段由xstart和xending表示。可以假设所有线段都在x轴(x -axis.Also )上。线段可以重叠。还有比O(n)更好的解决方案吗？我认为，如果线段没有重叠排序和二进制搜索，trick.There就会有很多点，我想找出每条线段上的点的数量

浏览 0提问于2013-08-11得票数 0

2回答

加权区间总和的优化

algorithm、optimization

我在真实的线上有M个间隔，每一个都有一个正的权重。我需要在它们中选择N，这样它们就不会重叠，并给出最大和。我怎么能有效地做到这一点呢？如果没有N个不重叠区间的子集，就没有解.没有不重叠的约束，问题很简单:选择N个最大的权重。因为有了约束，这已经不能用了。在我的例子中，N和M是小的(<20)，但是我希望有一个比尝试所有子集更有效的<

浏览 3提问于2016-06-22得票数 1

回答已采纳

2回答

总权重为W的非重叠区间的最大总和

algorithm、dynamic-programming

给定一个N整数和一个正整数W的序列S，找出一组不重叠的区间，使得它们的总权重恰好是W，并且它们的总和是最大化的。total_sum = Sum([1,2]) + Sum([4,5]) = 9 + 8 = 17 这个问题听起来有点像背包问题和加权间隔调度，但我认为这个问题可以用一种更简单的方式解决我的想法是使用动态编程，让P[i][k] be the maximum t

浏览 1提问于2013-03-10得票数 2

2回答

具有作业间隔时间的动态规划区间调度

algorithm、dynamic、recursion、scheduling、intervals

我正在尝试用动态规划来编程区间调度问题。所有作业都有不同的(正)权重，并且不会重叠。这些权重代表不同的运行时间。作业之间可能存在三个“间隙”的空闲时间。此外，每个作业的每个时间单位(以秒为单位)占用一个资源。这些资源都可以有不同的值。我想用动态编程算法(递归)为所有作业找到最小的资源总和。作业1需要两个时间单位，因此需要两个资源，因为它是第一个作

浏览 2提问于2012-12-21得票数 1

回答已采纳

2回答

带依赖作业的加权区间调度/具有多个所需运行时间的作业

algorithm、graph-algorithm、memoization、knapsack-problem

区间调度算法基本上是基于按结束时间排序作业的，但是如果调度作业A意味着您必须调度作业C，那么该怎么办？你不能只运行程序A的10-11部分。或者，说程序运行星期一，韦德，星期五，但在不同的时间每天。最短路径算法，在每周的每一天，你同时遍历7张图，每一张图都排序，只连接后面的程序。如果你选择星期一的节目A，你选择它在所有的日子，就像这样。如果程序需要在一天内运行两次，这个解决方案不能解决这个问题。为n个程序生成n×n矩阵，并检查每个程序

浏览 3提问于2017-09-02得票数 0

回答已采纳

1回答

找出不与点重叠的所有间隔

algorithm、computational-geometry

., (an, bn)的间隔。给定一个点，找出不与点重叠的所有间隔。如果我们想找出与点重叠的区间，则区间树是一种简单的解决方案。当我们想要找到不相交的间隔时，情况如何？

浏览 2提问于2015-07-23得票数 2

2回答

如何最小化最短路径树的总代价

graph-theory、shortest-path

我有一个边权为正的有向无环图。它具有单个源和一组目标(距离源最远的顶点)。我找到从源到每个目标的最短路径。其中一些路径是重叠的。我想要的是一个最短路径树，它最小化所有边的权重总和。假设所有边的权重相等，如果它们在大部分长度内共享一条最短路径，那么这比两条基本上不重叠的最短路径更可取(树中的边越少，总成本就越低)

浏览 2提问于2010-05-08得票数 7

2回答

如何有效地实现这个子集枚举问题？

python、algorithm

我有一个数字列表Sn = [a, b, c, d, ...]和一组不重叠的间隔Si = {I1, I2, I3, ...}。鉴于此，我的问题是找到Sn子集的列表L，使得每个子集中的元素总和至少绑定到Si中的一个区间中。我现在的方法是枚举Sn的所有子集，并根据它们是否符合某个区间进行过滤。它是正确的，但效率很低。30), (12, 6), (12

浏览 30提问于2020-09-08得票数 1

2回答

选择一组值之和最高的区间的算法

c++、algorithm、time-complexity、intervals

如何以尽可能有效的方式解决以下问题(也许是线性复杂性)？我正在考虑将其实现为带有计算边的图形，并可能使用Djikstra或类似的东西。但问题是插入到图形中，这将花费太多

浏览 1提问于2016-11-29得票数 1

0回答

2021-09-28：合并区间。以数组 intervals 表示若干个区间的集合，其中单个区间为？

编程算法

2021-09-28：合并区间。以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。力扣56。

浏览 246提问于2021-09-28

1回答

寻找重叠加权多边形的最高“区域”

python、algorithm、maps、shapes、polygons

我有许多多边形，它们是以坐标列表的形式出现的。这些多边形中的每一个都代表着全球地图上的一个区域，每个多边形都有一个权重。我需要在地图上找到这个重量最高的区域。这意味着，在多边形重叠的地方，权重将是相交区域的两个多边形的总和。我想使计算尽可能有效。任何帮助都将不胜感激。

浏览 5提问于2016-01-18得票数 1

回答已采纳

2回答

区间树的实际应用

data-structures、tree、interval-tree

我在谷歌上搜索过这个话题，并在上找到了这个。 P.S:对于更多关于间隔树的

浏览 8提问于2015-04-15得票数 2

2回答

Swift:在多个范围之间生成随机数

swift、random、range

.-8和3...8let zeroOrOne = CGFloat.random(in: 0...1)} else {} 但我想知道是否有更好的方法来做到这一点

浏览 0提问于2019-04-15得票数 1

回答已采纳

1回答

求O(nlog(n))中的“最大”重叠间隔对

algorithm、sorting、search、intervals

问题陈述输出对间隔；{s_i、t_i、s_j、t_j}，所有间隔对之间的最大重叠。示例->可能有6个区间对。在这些对中，1,10和3,15有最大可能重叠的7对。产出：{1,10,3,15} 朴素算法将是一种蛮力方法，在跟踪当前最大重叠值的同时，将所有n个区间进行比较。

浏览 1提问于2016-09-04得票数 12

回答已采纳

1回答

求点最小权覆盖的动态规划

algorithm、dynamic-programming

，在真实的线路上。π的位置由它的坐标xi给出。也给出m间隔I1，I2，。。。，I= 。每个区间j都有一个非负权重wj .如果xi∈aj，bj，则称区间Ij覆盖π。子集S⊆{I1，I2，.。。区间的Im}是给定点的覆盖，如果对于每个π，1≤i≤n，S中有一个区间覆盖π。在图中，用粗体表示的间隔是对点的覆盖。目标是找出点的最小重量覆盖。请注意，最小重量罩可能与间隔最

浏览 1提问于2016-03-27得票数 1

回答已采纳

5回答

用于处理间隔的数据结构

algorithm、data-structures、tree、intervals

我得到了一系列不能重叠的时间间隔(t_start，t_end)，即: t_end(i) > t_start(i+1)。我想做以下操作：2)取间隔[ (1,7) - (3,5) = {(1,3)，(5,7)}4)在某个点{(1,4)，(7，8)}之后找到第一

浏览 3提问于2009-12-31得票数 13

回答已采纳

1回答

不重叠区间的所有极大子集的输出敏感快速枚举

algorithm

因此，给定一组区间，找到具有最大间隔数的非重叠区间的子集，可以在按其右端点对区间进行排序之后，在线性时间内完成。但是，如果我们想要输出具有最大数目的不重叠间隔的所有解子集，该怎么办？运行时间应该是输出敏感的，因为在n个间隔内，最优解的数目可以是指数的，例如，高达O(sqrt(n)^sqrt(n))。因此，如果存在S最优解，它们是否能与S的大小成线

浏览 3提问于2014-07-11得票数 0

回答已采纳

2回答

带R的加权总体比例置信区间的确定

r、categorical-data、confidence-interval、weighted、population

任务:计算一个范畴变量的表现形式的加权份额，并在这些加权股票周围找到置信区间。：ci.share <- function(category, manifestationmanifestation = i)使结果易于读懂： cis <- t(sapply(cis, "[&qu

浏览 7提问于2020-03-11得票数 1

回答已采纳

点击加载更多