What is the best way to solve Car Fleet?

The optimized O(n) approach using Stack patterns is generally preferred.

상위 150개 인터뷰쉬움

자동차 함대

'Car Fleet' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

1차선 도로를 따라 같은 목적지로 가는 자동차가 n 대 있습니다. 목적지는 target 마일 떨어져 있습니다.

두 개의 정수 배열 position 및 speed이 제공되며 둘 다 길이는 n입니다. 여기서 position[i]는 i번째 자동차의 위치이고 speed[i]은 i번째 자동차의 속도(시간당 마일)입니다.

자동차는 결코 앞서가는 다른 차를 추월할 수 없지만, 그 차를 따라잡아 같은 속도로 범퍼에서 범퍼로 주행할 수 있습니다. 더 빠른 자동차는 더 느린 자동차의 속도에 맞춰 속도를 늦춥니다. 이 두 자동차 사이의 거리는 무시됩니다(같은 위치에 있는 것으로 가정).

자동차 함대는 동일한 위치와 동일한 속도로 주행하는 비어 있지 않은 자동차 세트입니다. 자동차 한 대도 자동차 함대입니다.

목적지에 도착할 자동차 함대의 수를 반환합니다.

carFleet(target: int, position: List[int], speed: List[int]) -> int 함수를 작성하세요.

제약

•n == len(position) == len(speed)
•1 <= n <= 10^5
•0 < target <= 10^6
•0 <= position[i] < target
•0 < speed[i] <= 10^6
•All positions are unique

예

Example 1

Input

target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

Output

Explanation

Cars at positions 10 and 8: car at 8 catches car at 10 (both arrive at time 1), forming 1 fleet. Car at 0: arrives at time 12. Car at 5: arrives at time 7. Car at 3: arrives at time 3, catches car at 5 at time 7, but car at 5 arrives at 7 too. Cars at 3 and 5 form a fleet. Total: 3 fleets.

Example 2

Input

target = 10, position = [3], speed = [3]

Output

Explanation

Only one car, so one fleet.

Example 3

Input

target = 100, position = [0, 2, 4], speed = [4, 2, 1]

Output

Explanation

All cars eventually form a single fleet.

Need a Hint?

세트나 힙과 같은 스택별 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

스택 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def car_fleet_opt(target, position, speed):
    pair = [[p, s] for p, s in zip(position, speed)]
    stack = []
    for p, s in sorted(pair)[::-1]:
        stack.append((target - p) / s)
        if len(stack) >= 2 and stack[-1] <= stack[-2]:
            stack.pop()
    return len(stack)

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def car_fleet_brute(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    times = [(target - p) / s for p, s in cars]
    fleets = 0
    curr_max_time = 0
    for t in times:
        if t > curr_max_time:
            fleets += 1
            curr_max_time = t
    return fleets