输入一系列元组并寻找交集

Question

广告牌被分成垂直的条带，每个条带的宽度都相同。一系列的海报相继贴在木板上。海报与广告牌本身的高度相同，贴在广告牌的不同位置，从而准确地覆盖了一系列的条状物。然而，海报的宽度不尽相同，而且可能是贴在一起的。多少海报最终（部分）可见。 编写一个可见函数，该函数包含一个元组列表，其中每个元组包含两个整数。元组描述贴在广告牌上的一系列海报的位置和顺序。第一个元组对应于首先附加的海报。最后一个元组的海报是附加在最后。元组的第一个整数表示海报左侧覆盖的条带的索引，第二个整数表示海报覆盖的条带数。函数应该返回最终（部分）可见的海报数量

问题是可用的：https://www.spoj.com/problems/PROG0412.pdf

def zichtbaar(l):
    count = 0, 0
    breedte = []
    for item in l:
        positie = tuple((item[0], item[0] + item[1]))

    if positie[0] >= count[0]:
        count = positie
        print(count)

zichtbaar([(1, 4), (2, 5), (8, 3), (3, 2), (7, 4)])

我不知道怎么解决这个问题

Answer 1

我试过做这个：

def billboard_creator(seq):
    seq = [sum(elem) for elem in seq]
    bill_len = max(seq)-1
    return ['']  * bill_len

def find_posters(billboard, posters):
    for posternum, (start, length) in enumerate(posters):
        billboard[start : start + length] = [posternum] *  length
    return billboard


post_seq = [(1, 4), (2, 5), (8, 3), (3, 2), (7, 4)]

def find_post_num(post_seq):
    empty_billboard = billboard_creator(post_seq)
    final_billboard = find_posters(empty_billboard, post_seq)
    if '' in final_billboard:
        return len(set(final_billboard))-1
    return len(set(final_billboard))

print(find_post_num(post_seq))

请注意，这根本不是解决问题的最佳方法，但我认为它有助于理解如何解决问题

所以我把问题分为三个主要部分： 在第一部分中，我做了一个函数来求广告牌的最小长度。我通过找到海报的开始和长度具有最大值的海报，然后返回一个由n个空字符串组成的列表，其中n是最大值减去1（因为海报，例如，在海报（7，4）中，海报从7开始，而不是8）

然后我做了另一个函数，循环遍历海报序列，并用海报替换空的广告牌的索引（根据海报的post\ seq中的索引在广告牌中放置一个不同的值）

然后在最后一个函数中调用这两个函数，检查公告牌中的所有唯一值，如果有“”，则减去一个（因此那里没有海报）

我尝试了提供的所有3个测试用例，结果都成功了

希望这有帮助