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

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 is_poster_visible(poster, covered_dict):
  for coord in range(poster[0], poster[0]+poster[1]):
    if not covered_dict.get(coord):
      return True
  return False

def output_visible_posters(poster_input):
  rev_input = poster_input.copy()
  rev_input.reverse()
  covered_dict = {}
  visible_posters = []
  for poster in rev_input:
    if is_poster_visible(poster, covered_dict):
      #if poster is visible, have to put in dict that some parts are now covered
      for coord in range(poster[0], poster[0] + poster[1]):
        covered_dict[coord] = True
      visible_posters.append(poster)
  return visible_posters  

这将为您提供部分可见的海报列表。要获取数字，只需返回列表的长度

Answer 2

我试过做这个：

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个测试用例，结果都成功了

希望这有帮助