RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1574759
Accepted
Aycon
Aycon
Asked:2024-04-05 15:49:41 +0000 UTC2024-04-05 15:49:41 +0000 UTC 2024-04-05 15:49:41 +0000 UTC

选择最佳间隔重叠

  • 772

我有几个加权间隔的列表 - 这些是元组(value, start, stop):

#   0   1   2   3   4   5   6   7   8   9   10
# 1         [___]                           
# 2 [___________________________________]   
# 3 [_______]                               
# 8     [_______________________]           
# 7                     [___________________]
# 6                                 [___]   
# 4     [_______________________]           

# input
# (value: float, start: float, stop: float)
list_in = [(2, 0, 9), (3, 0, 2), (8, 1, 7), (4, 1, 7), (1, 3, 4), (5, 5, 10), (6, 8, 9)]

我想找到所有部分重叠并选择“最佳”重叠,即 最大的重叠value。

对于我的示例,正​​确答案是:

#   0   1   2   3   4   5   6   7   8   9   10
# 1                                         
# 2                                         
# 3 [___]                                   
# 8     [_______________________]           
# 7                             [___________]
# 6                                         
# 4                                         

# output
list_out = [(3, 0, 1), (8, 1, 7), (7, 7, 10)]

我会尽量保持简单,说明我所拥有的所有条件,但以下是您应该了解的最低限度:

  1. 输入的元组数组未以任何方式排序
  2. 我有一个区间树的实现,如果算法性能更高或更简单,请使用它

3)需要考虑-float('inf')区间的开始和float('inf')区间的结束。

  1. 如果两个间隔的值value相同,则越短越好。如果它们的长度相同,则它是间隔的精确副本 - 忽略精确副本。
  2. 忽略具有的间隔start == stop

如果这对您来说更容易,以下是相对间距的所有可能情况:

# Target interval:
#   0   1   2   3   4   5   6   7   8   9
#               [___________]           

# All cases for target:
#   0   1   2   3   4   5   6   7   8   9
#   [_______]                           
#       [_______]                       
#           [_______]                   
#               [_______]               
#                   [___]               
#                       [_______]       
#                           [_______]   
#                               [_______]
#           [___________________]       
#               [___________]           

区间和点的所有情况:

value, start, stop = interval
point = x

point < start
point == start
start < point and point < stop
point == stop
stop < point

我正面解决这个问题的任何尝试都会导致组合爆炸并将代码变成回调地狱

请帮忙。PS:我可以粘贴我的尝试,但它需要 200 行代码,并且开始如下:

def calc_factor(integral_value: float, depth_start: float, depth_stop: float):
    return integral_value / (depth_stop - depth_start)

def split_by_intersections(interval_l: IntegralValueInterval, interval_r: IntegralValueInterval):
    assert interval_l.depth_start < interval_l.depth_stop
    assert interval_r.depth_start < interval_r.depth_stop
    assert interval_l.depth_start > -float('inf')
    assert interval_l.depth_stop < float('inf')
    assert interval_r.depth_start > -float('inf')
    assert interval_r.depth_stop < float('inf')
    
    # if-hell I know this, but I don't know how to simplify it.
    if interval_l.depth_start < interval_r.depth_start:
        if interval_l.depth_stop < interval_r.depth_start:
            # L.start L.stop R.start R.stop
            return [interval_l, interval_r]
        
        elif interval_l.depth_stop == interval_r.depth_start:
            # L.start (L.stop R.start) R.stop
            interval_l.depth_stop -= settings.gis_delta_depth
            return [interval_l, interval_r]
        
        elif interval_l.depth_stop > interval_r.depth_start and interval_l.depth_stop < interval_r.depth_stop:
            # L.start R.start L.stop R.stop
            a = interval_l.depth_start
            b = interval_r.depth_start
            c = interval_l.depth_stop
            d = interval_r.depth_stop
            
            interval_l.depth_start = a
            interval_l.depth_stop = b - settings.gis_delta_depth
            
            interval_c = IntegralValueInterval()
            interval_c.depth_start = b
            interval_c.depth_stop = c - settings.gis_delta_depth
            left_factor = calc_factor(interval_l.integral_value, interval_c.depth_start, interval_c.depth_stop)
            right_factor = calc_factor(interval_r.integral_value, interval_c.depth_start, interval_c.depth_stop)
            if left_factor < right_factor:
                interval_c.integral_value = interval_r.integral_value
            else:
                interval_c.integral_value = interval_l.integral_value
                
            interval_r.depth_stop = d
            interval_r.depth_start = c
            
            return [interval_l, interval_c, interval_r]
        
        elif interval_l.depth_stop == interval_r.depth_stop:
            # L.start R.start (L.stop R.stop)
            left_factor = calc_factor(interval_l.integral_value, interval_l.depth_start, interval_l.depth_stop)
            right_factor = calc_factor(interval_r.integral_value, interval_r.depth_start, interval_r.depth_stop)
            if left_factor < right_factor:
                interval_l.depth_stop = interval_r.depth_start - settings.gis_delta_depth
            else:
                interval_r.depth_start = interval_l.depth_stop
                interval_l.depth_stop -= settings.gis_delta_depth
            
            return [interval_l, interval_r]
...

PS 2.0:我尝试为所有情况编写测试,发现不可能考虑到-float('inf'),float('inf')因为存在矛盾的例子,例如,[(2, -float('inf'), 6), (1, -float('inf'), 2)]不清楚哪个段更好。因此,我正在修改这个问题。


PS 3.0:我在代码中附上了“测试”,以便您可以检查您的解决方案。

def test():
    for intervals, expected in (
        # value left > value right
        ([(2, 3, 6), (1, 0, 2)], [(1, 0, 2), (2, 3, 6)]),
        ([(2, 3, 6), (1, 1, 3)], [(1, 1, 3), (2, 3, 6)]),
        ([(2, 3, 6), (1, 2, 4)], [(1, 2, 3), (2, 3, 6)]),
        ([(2, 3, 6), (1, 3, 5)], [(2, 3, 6)]),
        ([(2, 3, 6), (1, 4, 5)], [(2, 3, 6)]),
        ([(2, 3, 6), (1, 3, 6)], [(2, 3, 6)]),
        ([(2, 3, 6), (1, 2, 6)], [(1, 2, 3), (2, 3, 6)]),
        ([(2, 3, 6), (1, 2, 7)], [(1, 2, 3), (2, 3, 6), (1, 6, 7)]),
        ([(2, 3, 6), (1, 3, 7)], [(2, 3, 6), (1, 6, 7)]),
        ([(2, 3, 6), (1, 4, 6)], [(2, 3, 6)]),
        ([(2, 3, 6), (1, 5, 7)], [(2, 3, 6), (1, 6, 7)]),
        ([(2, 3, 6), (1, 6, 8)], [(2, 3, 6), (1, 6, 8)]),
        ([(2, 3, 6), (1, 7, 9)], [(2, 3, 6), (1, 7, 9)]),
        
        # value left == value right
        ([(2, 3, 6), (2, 0, 2)], [(2, 0, 2), (2, 3, 6)]),               # 2 / (6 - 3) < 2 / (2 - 0)
        ([(2, 3, 6), (2, 1, 3)], [(2, 1, 3), (2, 3, 6)]),               # 2 / (6 - 3) < 2 / (3 - 1)
        ([(2, 3, 6), (2, 2, 4)], [(2, 2, 4), (2, 4, 6)]),               # 2 / (6 - 3) < 2 / (4 - 2)
        ([(2, 3, 6), (2, 3, 5)], [(2, 3, 5), (2, 5, 6)]),               # 2 / (6 - 3) < 2 / (5 - 3)
        ([(2, 3, 6), (2, 4, 5)], [(2, 3, 4), (2, 4, 5), (2, 5, 6)]),    # 2 / (6 - 3) < 2 / (5 - 4)
        ([(2, 3, 6), (2, 3, 6)], [(2, 3, 6)]),                          # 2 / (6 - 3) == 2 / (6 - 3) (copy)
        ([(2, 3, 6), (2, 2, 6)], [(2, 2, 3), (2, 3, 6)]),               # 2 / (6 - 3) > 2 / (6 - 2)
        ([(2, 3, 6), (2, 2, 7)], [(2, 2, 3), (2, 3, 6), (2, 6, 7)]),    # 2 / (6 - 3) > 2 / (7 - 2)
        ([(2, 3, 6), (2, 3, 7)], [(2, 3, 6), (2, 6, 7)]),               # 2 / (6 - 3) > 2 / (7 - 3)
        ([(2, 3, 6), (2, 4, 6)], [(2, 3, 4), (2, 4, 6)]),               # 2 / (6 - 3) < 2 / (6 - 4)
        ([(2, 3, 6), (2, 5, 7)], [(2, 3, 5), (2, 5, 7)]),               # 2 / (6 - 3) < 2 / (7 - 5)
        ([(2, 3, 6), (2, 6, 8)], [(2, 3, 6), (2, 6, 8)]),               # 2 / (6 - 3) < 2 / (8 - 6)
        ([(2, 3, 6), (2, 7, 9)], [(2, 3, 6), (2, 7, 9)]),               # 2 / (6 - 3) < 2 / (9 - 7)
        
        # value left < value right
        ([(2, 3, 6), (3, 0, 2)], [(3, 0, 2), (2, 3, 6)]),
        ([(2, 3, 6), (3, 1, 3)], [(3, 1, 3), (2, 3, 6)]),
        ([(2, 3, 6), (3, 2, 4)], [(3, 2, 4), (2, 4, 6)]),
        ([(2, 3, 6), (3, 3, 5)], [(3, 3, 5), (2, 5, 6)]),
        ([(2, 3, 6), (3, 4, 5)], [(2, 3, 4), (3, 4, 5), (2, 5, 6)]),
        ([(2, 3, 6), (3, 3, 6)], [(3, 3, 6)]),
        ([(2, 3, 6), (3, 2, 6)], [(3, 2, 6)]),
        ([(2, 3, 6), (3, 2, 7)], [(3, 2, 7)]),
        ([(2, 3, 6), (3, 3, 7)], [(3, 3, 7)]),
        ([(2, 3, 6), (3, 4, 6)], [(2, 3, 4), (3, 4, 6)]),
        ([(2, 3, 6), (3, 5, 7)], [(2, 3, 5), (3, 5, 7)]),
        ([(2, 3, 6), (3, 6, 8)], [(2, 3, 6), (3, 6, 8)]),
        ([(2, 3, 6), (3, 7, 9)], [(2, 3, 6), (3, 7, 9)]),
    ):
        actual = list(max_values(intervals))
        if actual != expected:
            print(intervals, expected, actual)


test()
python
  • 2 2 个回答
  • 135 Views

2 个回答

  • Voted
  1. Best Answer
    Stanislav Volodarskiy
    2024-04-05T20:38:29Z2024-04-05T20:38:29Z

    问题通过扫地就解决了。事件是间隔的结束。事件队列是一个已排序的数组;如果各段的开始时间相等,则这些段会排到末尾。状态:覆盖给定点的线段集。集合的结构是支持删除元素的最大值堆。

    事件处理:

    • 如果这是段的开头,则将其值添加到集合中
    • 如果这是段的末尾,则将其标记为在集合中已删除

    要打印结果,将存储当前最大值的开头(如果有)和当前最大值本身。如果在此事件中最大值发生变化,

    • 打印一个三元组(最大值、开始、当前事件);
    • 更新起始值和当前最大值。
    import heapq
    
    
    def min_values(intervals):
        # event queue
        events = [] # (x, is_end, index, value, label)
        for index, (start, stop, value, label) in enumerate(intervals):
            events.append((start, False, index, value, label))
            events.append((stop , True , index, value, label))
        events.sort()
    
        # status
        deleted = [False] * (len(events) // 2)
        heap = []
    
        # print
        last_start = None
        last_value = None
        last_label = None
    
        for x, is_end, index, value, label in events:
            # update status
            if is_end:
                deleted[index] = True
            else:
                heapq.heappush(heap, (value, index, label))
    
            # remove deleted items from heap top
            while heap and deleted[heap[0][1]]:
                heapq.heappop(heap)
            
            # print
            value = heap[0][0] if heap else None
            label = heap[0][2] if heap else None
            if value != last_value:
                if last_value is not None and last_start < x:
                    yield last_label, last_start, x 
                last_start = x
                last_value = value
                last_label = label
    
    
    def max_values(intervals):
        return min_values(
            (start, stop, (-value, stop - start), value)
            for value, start, stop in intervals
        )
    
    
    def test():
        for intervals, expected in (
            # value left > value right
            ([(2, 3, 6), (1, 3, 6)], [(2, 3, 6)]),
            ([(2, 3, 6), (1, 0, 2)], [(1, 0, 2), (2, 3, 6)]),
            ([(2, 3, 6), (1, 1, 3)], [(1, 1, 3), (2, 3, 6)]),
            ([(2, 3, 6), (1, 2, 4)], [(1, 2, 3), (2, 3, 6)]),
            ([(2, 3, 6), (1, 3, 5)], [(2, 3, 6)]),
            ([(2, 3, 6), (1, 4, 5)], [(2, 3, 6)]),
            ([(2, 3, 6), (1, 5, 7)], [(2, 3, 6), (1, 6, 7)]),
            ([(2, 3, 6), (1, 6, 8)], [(2, 3, 6), (1, 6, 8)]),
            ([(2, 3, 6), (1, 7, 9)], [(2, 3, 6), (1, 7, 9)]),
            ([(2, 3, 6), (1, 2, 7)], [(1, 2, 3), (2, 3, 6), (1, 6, 7)]),
            
            # value left == value right
            ([(2, 3, 6), (2, 3, 6)], [(2, 3, 6)]), # is copy
            ([(2, 3, 6), (2, 0, 2)], [(2, 0, 2), (2, 3, 6)]), # 2. / (6. - 3.) < 2. / (2. - 0.)
            ([(2, 3, 6), (2, 1, 3)], [(2, 1, 3), (2, 3, 6)]), # 2. / (6. - 3.) < 2. / (3. - 1.)
            ([(2, 3, 6), (2, 2, 4)], [(2, 2, 4), (2, 4, 6)]), # 2. / (6. - 3.) < 2. / (4. - 2.)
            ([(2, 3, 6), (2, 3, 5)], [(2, 3, 5), (2, 5, 6)]), # 2. / (6. - 3.) < 2. / (5. - 3.)
            ([(2, 3, 6), (2, 4, 5)], [(2, 3, 4), (2, 4, 5), (2, 5, 6)]), # 2. / (6. - 3.) < 2. / (5. - 4.)
            ([(2, 3, 6), (2, 5, 7)], [(2, 3, 5), (2, 5, 7)]), # 2. / (6. - 3.) < 2. / (7. - 5.)
            ([(2, 3, 6), (2, 6, 8)], [(2, 3, 6), (2, 6, 8)]), # 2. / (6. - 3.) < 2. / (8. - 6.)
            ([(2, 3, 6), (2, 7, 9)], [(2, 3, 6), (2, 7, 9)]), # 2. / (6. - 3.) < 2. / (9. - 7.)
            ([(2, 3, 6), (2, 2, 7)], [(2, 2, 3), (2, 3, 6), (2, 6, 7)]), # 2. / (6. - 3.) > 2. / (7. - 2.)
            
            # value left < value right
            ([(2, 3, 6), (3, 3, 6)], [(3, 3, 6)]),
            ([(2, 3, 6), (3, 0, 2)], [(3, 0, 2), (2, 3, 6)]),
            ([(2, 3, 6), (3, 1, 3)], [(3, 1, 3), (2, 3, 6)]),
            ([(2, 3, 6), (3, 2, 4)], [(3, 2, 4), (2, 4, 6)]),
            ([(2, 3, 6), (3, 3, 5)], [(3, 3, 5), (2, 5, 6)]),
            ([(2, 3, 6), (3, 4, 5)], [(2, 3, 4), (3, 4, 5), (2, 5, 6)]),
            ([(2, 3, 6), (3, 5, 7)], [(2, 3, 5), (3, 5, 7)]),
            ([(2, 3, 6), (3, 6, 8)], [(2, 3, 6), (3, 6, 8)]),
            ([(2, 3, 6), (3, 7, 9)], [(2, 3, 6), (3, 7, 9)]),
            ([(2, 3, 6), (3, 2, 7)], [(3, 2, 7)]),
        ):
            actual = list(max_values(intervals))
            if actual != expected:
                print(intervals, expected, actual)
    
    
    test()
    
    • 3
  2. Akina
    2024-04-05T17:36:38Z2024-04-05T17:36:38Z

    我用原始数据来展示它。

    步骤 1-1。收集积分。之后我们得到一个数组

    0,1,2,3,5,7,8,9,10
    

    步骤 1-2。转换为最小间隔。我们得到一套

    0-1
    1-2
    2-3
    3-5
    5-7
    7-8
    8-9
    9-10
    

    步骤 2. 对于每个区间,选择与其重叠的初始区间,收集权重,选择最大值

    0-1 重量 2, 3
    1-2 重量 2.3 , 8,4
    2-3 重量 1.2 , 8,4
    3-5 权重 2, 8 , 4
    5-7 权重 2 , 8,7,4
    7-8 重量 2, 7
    8-9 权重 2, 7 , 6
    9-10 重量7

    步骤 3. 如果相邻区间的权重相等,我们将它们合并。我们得到

    0-1 重量 2, 3 总计 0-1 重量 3
    1-2 重量 2.3 , 8,4
    2-3 重量 1.2 , 8,4
    3-5 权重 2, 8 , 4
    5-7 权重 2 , 8,7,4 总计 1-7 重量 8
    7-8 重量 2, 7
    8-9 权重 2, 7 , 6
    9-10 重量7 总计 7-10 重量 7
    • 1

相关问题

  • 是否可以以某种方式自定义 QTabWidget?

  • telebot.anihelper.ApiException 错误

  • Python。检查一个数字是否是 3 的幂。输出 无

  • 解析多个响应

  • 交换两个数组的元素,以便它们的新内容也反转

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    我看不懂措辞

    • 1 个回答
  • Marko Smith

    请求的模块“del”不提供名为“default”的导出

    • 3 个回答
  • Marko Smith

    "!+tab" 在 HTML 的 vs 代码中不起作用

    • 5 个回答
  • Marko Smith

    我正在尝试解决“猜词”的问题。Python

    • 2 个回答
  • Marko Smith

    可以使用哪些命令将当前指针移动到指定的提交而不更改工作目录中的文件?

    • 1 个回答
  • Marko Smith

    Python解析野莓

    • 1 个回答
  • Marko Smith

    问题:“警告:检查最新版本的 pip 时出错。”

    • 2 个回答
  • Marko Smith

    帮助编写一个用值填充变量的循环。解决这个问题

    • 2 个回答
  • Marko Smith

    尽管依赖数组为空,但在渲染上调用了 2 次 useEffect

    • 2 个回答
  • Marko Smith

    数据不通过 Telegram.WebApp.sendData 发送

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5