3

问题如下：-

给定 N 头不同大象的寿命，用一对整数表示。

前任。[5,10] [6,15] [2,7] 表示一头大象从 5 年到 10 年。第二只从 6 年到 15 年，依此类推。

你可以假设一头大象最多只能活 M 年。（不是问题的一部分，但我们可能需要它来表示算法复杂性。）

给定这些数据，找出最大数量的大象生活的年份。随意解决关系。

我已经尝试了几种方法来解决这个问题，但似乎没有什么比天真的解决方案的复杂性更重要的了。天真的解决方案是： -

1. Maintain an array(call it ctr).
2. For every set you encounter, 
    increment all values of ctr in that range.
3. Once you have traversed all sets, 
    find the index with the highest value in ctr.

很容易看出复杂度将是 O(N*M)。

谁能提供更好的解决方案？

另一个问题是：是否存在可以在 O(1) 时间内更改一系列值的数据结构？在数组中，要修改 k 个元素，显然需要 O(k) 时间。有更好的吗？

4

2 回答 2

8

将范围的左端视为 +1 大象活着，而将范围的右端视为 -1 大象活着。将这些 +1 和 -1 标记放在数轴上，然后在数轴上按从左到右的排序顺序排列。当你走在数轴上时，跟踪当前活着的大象数量（只需将 +1 和 -1 相加），并将其与活着的最大大象数量和相应年份进行核对。然后你就有了一个很好的 O(n log n) 时间解决方案。

请注意，您必须在簿记方面小心一点，以在当年处理 +1 之前的 -1，或者仅在处理给定年份内的所有数据后更新您的最大值。

于 2012-12-30T16:59:03.480 回答
2

这是基于“扫描线”技巧的@rrenaud 在 Python 中的答案的实现：

#!/usr/bin/env python
ranges = [5,10], [6,15], [2,7]

BORN, DIE = 1, 0 # values define sorting order within the same year
events = sorted(event # sort start 'born' and end 'die' events together by year,
                      # process 'die' before 'born' in the same year
                for r in ranges  for event in zip(r, (BORN, DIE)))

max_nelephants = nelephants = 0
prev_year = events[0][0]
for year, born_or_die in events:
    if prev_year != year: # done processing a year
        prev_year = year
        max_nelephants = max(max_nelephants, nelephants)
    nelephants += (born_or_die == BORN) # increase number of alive elephants
    nelephants -= (born_or_die == DIE)  # decrease number of alive elephants
max_nelephants = max(max_nelephants, nelephants)
print(max_nelephants)
于 2012-12-30T18:41:33.713 回答