Minimum Platforms

Q: 최소 플랫폼 문제의 시간 복잡도는 얼마인가요?

두 배열을 정렬하는 데 O(n log n) 이 들고, 그 이후의 스윕에는 O(n) 이 들기 때문에 정렬이 지배적입니다. 정렬된 복사본은 추가 공간 O(n) 을 차지합니다.

Q: minimum platforms는 meeting rooms II와 어떻게 다른가요?

둘 다 한 시점에 겹치는 구간의 최대 개수를 묻습니다. 여기서는 열차가 출발하는 순간이 포함된 1분 동안 플랫폼을 점유하고, Meeting Rooms II에서는 회의가 끝나는 순간 회의실을 사용할 수 있습니다. 스위프 과정에서는 이 차이가 비교 하나로 나타납니다. 동률이면 여기서는 도착을 먼저 처리하고, 저기서는 끝나는 회의를 먼저 처리합니다.

Q: 정렬 없이 최소 플랫폼 수를 구할 수 있을까요?

네, 매번 고정된 시각에 맞춰지기 때문입니다. 2401개의 카운터를 HHMM 숫자로 인덱싱하고, 도착 시마다 1을 더하고 departure + 1 에서 1을 뺍니다. 누적 합의 최댓값이 정답입니다. 시간 복잡도는 O(n + 2400) 입니다. 1260부터 1299까지의 인덱스는 시각이 아니므로 도착이 없으며, 따라서 최댓값을 만들지 않습니다.

보통정렬 그리디 투 포인터

+10

한 역의 하루 시간표가 주어집니다. 열차 i는 arrival[i]에 도착하고 departure[i]에 출발합니다. 시간은 콜론이 없는 시각을 나타내는 HHMM 숫자이므로, 930은 09:30입니다.

열차는 도착한 시각부터 출발한 시각까지 플랫폼을 점유하며, 도착 시각과 출발 시각 모두 포함됩니다. 따라서 다른 열차가 출발하는 시각에 도착하는 열차는 그 열차의 플랫폼을 사용할 수 없습니다.

열차가 기다릴 필요가 없도록 역에 필요한 최소 플랫폼 수를 반환하세요.

함수

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: 각 열차의 도착 시간(HHMM 형식의 숫자)
departureinteger-array: 각 열차의 출발 시간을 HHMM 숫자로 나타낸 값입니다. departure[i]는 arrival[i]에 해당합니다.
반환값integer: 같은 분에 역에 있는 열차의 최대 수이며, 필요한 플랫폼의 최소 개수입니다

제약 조건

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
각 시간은 유효한 HHMM 시간입니다. 마지막 두 자리는 최대 59입니다.
모든 기차는 같은 날 운행합니다. 배열은 정렬되어 있지 않습니다.

예제

입력: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
출력: 3
설명: 15:30에 역에는 세 대의 열차가 있습니다. 15:00부터 16:00까지 운행하는 열차, 15:20부터 15:35까지 운행하는 열차, 15:30부터 15:45까지 운행하는 열차입니다. 어느 분에도 열차가 네 대씩 있지는 않으므로 3개의 승강장이면 충분합니다.

입력: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
출력: 2
설명: 12:30에 도착하는 열차는 12:30에 출발하는 열차와 만나고, 13:00에도 같은 일이 일어납니다. 이 두 시각에는 각각 역에 열차가 두 대 있으므로, 답은 1이 아니라 2입니다.

입력: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
출력: 2
설명: 06:00부터 22:00까지 운행하는 열차는 하루 종일 한 플랫폼을 사용합니다. 07:00부터 07:15까지 운행하는 열차와 13:00부터 14:00까지 운행하는 열차는 절대 만나지 않으므로, 두 열차는 두 번째 플랫폼인 2를 공유합니다.

후속 질문

일부 야간 열차는 자정 전에 도착하고 자정이 지난 후에 출발하므로, 출발 시각의 숫자가 도착 시각보다 작습니다. 시간표가 자정을 넘기는 경우 플랫폼 수를 어떻게 셀 수 있을까요?

풀이

정답은 같은 분에 역에 있는 열차 수의 최댓값입니다. 모든 열차 쌍을 비교하지 않고 가장 붐비는 분을 찾는 것이 핵심입니다. 도착 시간과 출발 시간을 각각 정렬한 다음, 현재 열차 수를 세면서 하루의 일정들을 한 번 훑으면 O(n log n) 시간에 찾을 수 있습니다.

각 도착 시 열차 수를 세세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

같은 분에 도착하는 열차들은 서로 다른 플랫폼을 사용해야 하므로, 가장 혼잡한 분의 열차 수가 하한입니다. 이 수는 충분한 수이기도 합니다. 도착한 열차가 열린 모든 플랫폼이 점유된 것을 발견할 때만 새 플랫폼을 엽니다. 그 분에는 열린 각 플랫폼에 열차가 한 대씩 있고 새 플랫폼에도 한 대가 서게 되므로, 최댓값보다 많은 플랫폼을 열지 않습니다.

현재 있는 열차 수는 열차가 도착할 때만 늘어나므로, 가장 혼잡한 분은 어떤 열차가 도착한 분입니다. 각 열차 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

두 목록을 모두 정렬하고 두 포인터로 훑어보세요

핵심 아이디어

존재하는 열차의 수는 특정 시각까지 몇 대가 도착했고 몇 대가 떠났는지에만 달려 있으며, 어느 열차가 언제 떠나는지에는 달려 있지 않습니다. 따라서 도착 시각과 출발 시각을 서로 독립적인 두 목록으로 정렬하세요. 시간순으로 함께 살펴보면 그날의 사건이 됩니다. 도착은 열차를 더하고, 출발은 열차를 하나 줄입니다.

시각이 같으면 도착을 먼저 처리합니다. 떠나는 열차가 그 시각에도 승강장을 점유하고 있기 때문입니다. 첫 번째 예시에서는 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에서 1로 줄어듭니다.
HHMM 숫자를 빼는 것: 1300에서 1259를 빼면 41이지만, 두 시각은 1분 차이입니다. 두 시각을 비교하는 것은 안전하며, 풀이에서는 비교만 합니다.
도착 시간순으로 열차를 정렬한 뒤 각 열차를 바로 앞 열차와만 비교하는 것. 세 번째 예시에서 06:00부터 22:00까지 머무는 열차처럼 정차 시간이 긴 열차는 목록에서 훨씬 뒤에 있는 열차들과 겹칩니다.
같은 분에 도착하고 떠나는 열차를 건너뛰는 것. 10:00부터 10:00까지 정차하는 열차가 네 대라면 플랫폼 네 개가 필요합니다.

자주 묻는 질문3

최소 플랫폼 문제의 시간 복잡도는 얼마인가요?

두 배열을 정렬하는 데 O(n log n)이 들고, 그 이후의 스윕에는 O(n)이 들기 때문에 정렬이 지배적입니다. 정렬된 복사본은 추가 공간 O(n)을 차지합니다.

minimum platforms는 meeting rooms II와 어떻게 다른가요?

둘 다 한 시점에 겹치는 구간의 최대 개수를 묻습니다. 여기서는 열차가 출발하는 순간이 포함된 1분 동안 플랫폼을 점유하고, Meeting Rooms II에서는 회의가 끝나는 순간 회의실을 사용할 수 있습니다. 스위프 과정에서는 이 차이가 비교 하나로 나타납니다. 동률이면 여기서는 도착을 먼저 처리하고, 저기서는 끝나는 회의를 먼저 처리합니다.

정렬 없이 최소 플랫폼 수를 구할 수 있을까요?

네, 매번 고정된 시각에 맞춰지기 때문입니다. 2401개의 카운터를 HHMM 숫자로 인덱싱하고, 도착 시마다 1을 더하고 departure + 1에서 1을 뺍니다. 누적 합의 최댓값이 정답입니다. 시간 복잡도는 O(n + 2400)입니다. 1260부터 1299까지의 인덱스는 시각이 아니므로 도착이 없으며, 따라서 최댓값을 만들지 않습니다.

def minimumPlatforms(arrival, departure):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

예상 출력