3

非常に有名な問題が 1 つあります。私はここで同じことを尋ねています。
与えられた期間のゾウの数があります。ここでの期間は、生年から死亡年までを意味します。
最大数のゾウが生きている期間を計算する必要があります。

例：

1990 - 2013
1995 - 2000
2010 - 2020
1992 - 1999

Answer is   1995 - 1999

私はこれを解決しようと懸命に努力しましたが、解決できません。

どうすればこの問題を解決できますか?

ユーザーが任意の年のゾウの数を見つけるように求めたとき、私はアプローチを得ました。セグメント ツリーを使用することで、ゾウの期間が与えられるたびに、その期間が毎年 1 ずつ増加することで解決しました。この方法で解決できます。これを使用して上記の問題を解決できますか?

上記の質問については、高レベルのアプローチのみが必要です。自分でコーディングします。

4

4 に答える 4

9

  • 各日付範囲を開始日と終了日に分割します。

  • 日付を並べ替えます。開始日と終了日が同じ場合は、終了日を最初に置きます (そうしないと、空の日付範囲が最適となる可能性があります)。

  • カウント 0 から開始します。

  • スイープライン アルゴリズムを使用して日付を反復処理します。

    • 開始日を取得した場合:

      • カウントを増やします。

      • 現在のカウントが最後の最適なカウントよりも大きい場合は、カウントを設定し、この開始日を保存してフラグを設定します。

    • 終了日を取得した場合:

      • フラグが設定されている場合は、保存された開始日とこの終了日を、これまでの最良の間隔としてカウントと共に保存します。

      • フラグをリセットします。

      • カウントを減らします。

例：

入力用:

1990 - 2013
1995 - 2000
2010 - 2020
1992 - 1999

分割およびソート: ( S= 開始、E= 終了)

1990 S, 1992 S, 1995 S, 1999 E, 2000 E, 2010 S, 2013 E, 2020 E

それらを繰り返す：

count = 0
lastStart = N/A
1990: count = 1
      count = 1 > 0, so set flag
        and lastStart = 1990

1992: count = 2
      count = 2 > 0, so set flag
        and lastStart = 1992

1995: count = 3
      count = 3 > 0, so set flag
        and lastStart = 1995

1999: flag is set, so
        record [lastStart (= 1995), 1999] with a count of 3
      reset flag
      count = 2

2000: flag is not set
      reset flag
      count = 1

2010: count = 2
      since count = 2 < 3, don't set flag

2013: flag is not set
      reset flag
      count = 1

2020: flag is not set
      reset flag
      count = 0
于 2013-10-03T10:15:11.650 に答える
0

これはどう？

上記のすべてのデータがファイルに保存されているとします。「 - 」で区切られた 2 つの配列に読み取ります。

したがって、birthYear[]すべての誕生年をdeathYear[]含み、すべての死亡年を含むことがわかりました。

したがって、誕生年[] = [1990年、1995年、2010年、1992年]死亡年[] = [2013年、2000年、2020年、1999年]

最小の誕生年と最大の死亡年を取得します。キーを年、値をカウントとしてハッシュテーブルを作成します。

したがって、

HashTable<String, Integer> numOfElephantsAlive = new HashTable<String, Integer>();

次に、min(BirthYear) から max(BirthYear) まで、次の操作を行います。

Birth Year Array を反復処理し、BirthYear と対応する DeathYear の間のすべての年をカウント 1 で HashTable に追加します。キーが既に存在する場合は、それに 1 を追加します。したがって、最後のケースの場合:

1992 - 1999
HashTable.put(1992, 1)
HashTable.put(1993, 1)
and so on for every year.

Say, for example, you have a Hashtable that looks like this at the end of it:

Key    Value
1995     3
1996     3
1992     2
1993     1
1994     3
1998     1
1997     2
1999     2

ここで、ゾウの数が最大だった年の範囲が必要です。したがって、反復して最大値を持つ年を見つけてみましょう。これはとても簡単です。keySet() を繰り返し処理し、年を取得します。

ここで、連続した年の範囲が必要です。これは、次の 2 つの方法で行うことができます。

keySet() に対して Collections.sort() を実行し、最大値に達したら、連続するすべての場所を保存します。

したがって、1994 年の例で 3 をヒットすると、その後のすべての年を 3 でチェックします。これにより、最小年と最大年の組み合わせである範囲が返されます。

于 2013-10-03T09:32:49.667 に答える
0

1) シリーズの大きいものから年順に並べる。2) データ セット全体の最大系列の年数を数えます。3) 次に、最大数を特定します。4) 最大数は何年にもわたってあなたの答えです...これは Algo で行うことができます。

于 2015-07-28T12:39:57.630 に答える
0

おそらく1つのアプローチ：期間を繰り返します。今までの期間のリストを追跡します。注: 各ステップで、期間の数は 2 (既存の期間のリストと重複しない場合は 1) ずつ増加します。例えば

1990 - 2013
Period List contains 1 period { (1990,2013) }
Count List contains 1 entry { 1 }

 1995 - 2000
Period List contains 3 periods { (1990,1995), (1995,2000), (2000,2013) }
Count List contains 3 entries { 1, 2, 1 }

 2010 - 2020
Period List contains 5 periods { (1990,1995), (1995,2000), (2000,2010), (2010, 2013), (2013, 2020) }
Count List contains 5 entries { 1, 2, 1, 2, 1 }

 1992 - 1999
Period List contains 7 periods { (1990,1992), (1992,1995), (1995,1999), (1999,2000), (2000,2010), (2010, 2013), (2013, 2020) }
Count List contains 7 entries { 1, 2, 3, 2, 1, 2, 1 }
于 2013-10-03T10:02:25.923 に答える