NeetCode 150 [Stack]:medium 5/5

NeetCodeのSolutionを書いていく

Car Fleet

問題概要

同じ目的地を目指すn台の車が1レーンの高速を走行しています。
positionとspeedの2つの整数の配列が与えられます。
position[i]はi番目の車の位置をマイルで表します。
speed[i]はi番目の車の速度をマイル/時間で表します。
目的地はtargetマイル先にあります。
先行する車を抜くことはできず、追いつくことまでしかできず、先行する車と同じスピードで走行します。
自動車の隊は空ではない車のSetで同じ場所を同じスピードで走っています。
単体の車も隊とみなします。
もし、自動車が目的地に着くと同時に隊に追いついたら、その車は隊の一部とみなされます。

目的地に着く隊の数を返しなさい。

例

Input: target = 10, position = [1,4], speed = [3,2]
Output: 1

Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1]
Output: 3

制約

• n == positionの長さ == speedの長さ
• nは1以上1000以下
• ターゲットは1以上1000以下
• スピードは 1以上100以下
• 位置は0以上ターゲット未満
• 全ての位置の数字はユニークな正数

計算量：O(nlogn)
メモリ：O(n)

メモ

問題が長い！

ポイントは以下

• 車の位置で降順ソートする
• 降順ソートするのは先行するデータの速度がキャップになる(後段はそれ以上速度が出ない)ため
• ターゲットに着く時間は簡単に求められる。先行する車が、後段の車より遅い到着時刻になるときは隊が作られる。

データをソートする。
車の到着時刻を計算する。
1第目を到着時刻とする。
2台目から順に評価し、先行する車の到着時間より早い(値が小さい)場合はスキップ
遅い(値が大きい)場合は、新しい到着時刻とする。
上記を繰り返す。

from typing import List


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pseudo_arrival_times = []
        position, speed = map(list, zip(*sorted(zip(position, speed), reverse=True)))
        for p, s in zip(position, speed):
            pseudo_arrival_times.append((target - p) / s)

        arrival_times: List[int] = []
        for ptime in pseudo_arrival_times:
            if not arrival_times or arrival_times[-1] < ptime:
                arrival_times.append(ptime)

        return len(arrival_times)