Minimum Platforms
ある駅の1日分の時刻表があります。列車 i は arrival[i] に到着し、departure[i] に出発します。時刻はコロンを省いた HHMM 形式の数値です。そのため、930 は09:30を表します。
列車は到着した分から出発する分まで、両方の分を含めてホームを使用します。そのため、別の列車が出発する分に到着する列車は、その列車のホームを使うことはできません。
どの列車も待つ必要がないようにするために駅に必要なホームの最小数を返してください。
関数
- arrivalinteger-array
- 各列車の到着時刻をHHMM形式の数値で
- departureinteger-array
- 各列車の出発時刻をHHMM形式の数値で表したもの。departure[i] は arrival[i] に対応します
- 戻り値integer
- 同じ分に駅にいる列車の最大数。これが必要なプラットフォーム数の最小値です
制約
1 ≤ arrival.length == departure.length ≤ 50000 ≤ arrival[i] ≤ departure[i] ≤ 2359- どの時刻も有効な
HHMM形式の時刻です。末尾の2桁は最大59です。 - すべての列車は同じ日に運行します。配列はソートされていません。
例
- 入力
- arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
- 出力
- 3
- 説明
- 15:30には、駅に3本の列車が停車しています。15:00から16:00までの列車、15:20から15:35までの列車、15:30から15:45までの列車です。4本になる分はないため、
3本のホームで十分です。
- 入力
- arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
- 出力
- 2
- 説明
- 12:30に到着する列車は12:30に出発する列車と同時に駅にあり、13:00でも同じことが起こります。それぞれの時刻には駅に列車が2本あるため、答えは1ではなく
2です。
- 入力
- arrival = [600, 700, 1300]departure = [2200, 715, 1400]
- 出力
- 2
- 説明
- 06:00から22:00まで運行する列車は、終日1つのホームを使用します。07:00から07:15までの列車と13:00から14:00までの列車は決して同時に運行しないため、2つ目のホームを共有します：
2。
発展問題
夜行列車の中には、真夜中前に到着して真夜中を過ぎてから出発するものがあり、そのため出発時刻の数字が到着時刻の数字より小さくなります。時刻表が真夜中をまたぐ場合、ホームの数をどのように数えますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どの列車がどのホームを使うかは、ひとまず忘れてください。1日の中から任意の1分を選んでみましょう。その1分だけで、ホームはいくつ必要になるでしょうか？
駅にいる列車の数は、列車が到着したときだけ増え、出発したときだけ減ります。イベントを時刻順にたどりながら数を記録し、最も大きい数が答えです。同時刻の場合は到着を先に処理します。その1分間は、出発する列車がまだホームを使っているためです。
到着時刻と出発時刻を別々のリストとして並べ、それぞれにポインターを1つずつ置きます。次の到着時刻が次の出発時刻以前なら、列車を1本追加してピーク時の台数を記録します。それ以外の場合は列車を1本減らします。到着時刻がなくなったら終了します。
解説
答えは、同じ分に駅にいる列車の最大数です。作業のポイントは、列車のすべての組み合わせを比較せずに、最も混雑する分を見つけることです。到着時刻と出発時刻を別々に並べ替え、その日の出来事を一度たどりながら数を累積すれば、O(n log n)で見つけられます。
各到着時の列車の数を数える
正しいが、最大のテストでは終わらない
考え方
同じ分に停車している列車にはそれぞれ異なるホームが必要なので、最も混雑する分の列車数が下限となります。また、この数で十分です。到着した列車が、空いているホームをすべて使用中だと確認した場合にだけ、新しいホームを開けばよいからです。その分には、開いている各ホームに列車が1本ずつ停車しており、さらに新しいホームにも1本停車するため、ピーク時の列車数を超えてホームを開くことはありません。
停車中の列車数が増えるのは列車が到着するときだけなので、最も混雑する分は、いずれかの列車の到着時刻です。各列車 i について、arrival[j] ≤ arrival[i] ≤ departure[j] を満たす列車 j の数を数えます。列車は出発する分にもホームに停車しているため、どちらの比較にも ≤ を使います。
n 本の列車それぞれについて、ほかの n 本すべてを調べるため、計算量は O(n²) です。列車が5000本の場合、比較は2500万回になります。
アルゴリズム
most = 0に設定します。- 各列車
iについて、arrival[j] ≤ arrival[i] ≤ departure[j]を満たす列車jの数を数えます。 - その数が
mostより大きければ、その数を保存します。 mostを返します。
def minimumPlatforms(arrival, departure):
n = len(arrival)
most = 0
for i in range(n):
# trains standing at the station in the minute train i arrives
here = 0
for j in range(n):
if arrival[j] <= arrival[i] <= departure[j]:
here += 1
most = max(most, here)
return most両方のリストをソートし、2つのポインターで走査する
考え方
ある時点の列車数は、どの列車がいつ出発するかではなく、特定の分までに何本到着し、何本出発したかだけで決まります。そこで、到着時刻と出発時刻を、それぞれ独立したリストとしてソートします。時刻順にまとめて見ると、それらがその日の出来事になります。到着で列車が1本増え、出発で1本減ります。
時刻が同じ場合は到着を先に扱います。その分の間は、出発する列車がまだホームを使っているためです。最初の例では、1100の出発後に列車数は0に戻り、その後、1500、1520、1530の到着がすべて1535の出発より先に来るため、列車数は3に達します。
到着がなくなった後は、残りの出発によって列車数が減るだけなので、そこで処理を止めます。ソートの計算量は O(n log n) で、走査は最大でも 2n ステップです。
アルゴリズム
arrivalのコピーとdepartureのコピーをソートします。platforms、most、i、jを0に設定します。i < nの間、arrivals[i] ≤ departures[j]の場合は、platformsに 1 を加え、mostを更新してiを進めます。- そうでなければ、
platformsから 1 を引き、jを進めます。 mostを返します。
def minimumPlatforms(arrival, departure):
arrivals = sorted(arrival)
departures = sorted(departure)
n = len(arrivals)
platforms = 0 # trains at the station right now
most = 0
i = 0 # next arrival
j = 0 # next departure
while i < n:
if arrivals[i] <= departures[j]:
# the next event is an arrival; on a tie the leaving train is still there
platforms += 1
most = max(most, platforms)
i += 1
else:
platforms -= 1
j += 1
return most
落とし穴と境界ケース
- 包含条件が必要なところで
<と比較し、≤を使わないこと。2つ目の例では、到着する列車はそれぞれ、その分に出発する列車が使っていたホームを使えるため、答えは2から1に減ります。 HHMM形式の数値を引き算すること。1300から1259を引くと41ですが、時刻の差は1分です。比較するのは安全で、この解法では比較だけを行います。- 列車を到着時刻で並べ、それぞれを直前の列車とのみ比較すること。3つ目の例にある06:00から22:00までのような長時間の停車は、リストのずっと後ろにある列車と重なります。
- 同じ分に到着して出発する列車を飛ばすこと。10:00から10:00まで停車する列車が4本なら、ホームは4つ必要です。
よくある質問3
最小プラットフォーム問題の時間計算量はどれくらいですか？
2つの配列のソートには O(n log n) のコストがかかり、その後の走査には O(n) のコストがかかるため、ソートが支配的です。ソート済みのコピーには追加で O(n) の領域が必要です。
最小プラットフォーム数は「Meeting Rooms II」とどう違いますか？
どちらも、ある瞬間に重なる区間の最大数を求めます。ここでは、列車は出発する分の間もホームを占有します。一方、Meeting Rooms II では、会議が終了した瞬間に部屋が空きます。スイープ処理では、これは比較の違いが1つだけです。同時刻の場合、ここでは到着を先に処理し、あちらでは終了する会議を先に処理します。
最小プラットフォーム数は、ソートせずに求められますか？
はい、すべての時刻が固定された時計に当てはまるからです。HHMMの数値で2401個のカウンターをインデックス化し、到着時に1を加算し、departure + 1の位置で1を減算します。累積和の最大値が答えです。計算時間はO(n + 2400)です。1260から1299のようなインデックスは時刻ではなく、到着もないため、ピークになることはありません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def minimumPlatforms(arrival, departure):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
arrival = [900, 1500, 920, 1520, 1000, 1530] departure = [930, 1600, 1010, 1535, 1100, 1545]
期待される出力
3