3

質問は次のとおりです：-

整数のペアとして表される、N個の異なる象の寿命が与えられます。

元。[5,10] [6,15] [2,7]は、1頭の象が5年目から10年目まで生きていたことを意味し、2頭目は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

これは、 「スキャンライン」トリックに基づいたPythonでの@rrenaudの回答の実装です。

#!/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 に答える