# [Greedy, Classic]
# https://leetcode.com/problems/car-fleet/
# 853. Car Fleet

# N cars are going to the same destination along a one lane road.  The
# destination is target miles away.
#
# Each car i has a constant speed speed[i] (in miles per hour), and initial
# position position[i] miles towards the target along the road.
#
# A car can never pass another car ahead of it, but it can catch up to it,
# and drive bumper to bumper at the same speed.
#
# The distance between these two cars is ignored - they are assumed to have
# the same position.
#
# A car fleet is some non-empty set of cars driving at the same position and
# same speed.  Note that a single car is also a car fleet.
#
# If a car catches up to a car fleet right at the destination point, it will
# still be considered as one car fleet.
#
#
# How many car fleets will arrive at the destination?
#
#
# Example 1:
#
# Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
# Output: 3
# Explanation:
# The cars starting at 10 and 8 become a fleet, meeting each other at 12.
# The car starting at 0 doesn't catch up to any other car, so it is a fleet
# by itself.
# The cars starting at 5 and 3 become a fleet, meeting each other at 6.
# Note that no other cars meet these fleets before the destination, so the
# answer is 3.
#
# Note:
#
# 0 <= N <= 10 ^ 4
# 0 < target <= 10 ^ 6
# 0 < speed[i] <= 10 ^ 6
# 0 <= position[i] < target
# All initial positions are different.


class Solution(object):
    def carFleet(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """
        if not position:
            return 0

        position_speed = sorted(
            zip(position, speed), reverse=True
        )

        ret = 1
        prev_position, prev_speed = position_speed[0]
        prev_time = (target - prev_position) / float(prev_speed)

        for idx in range(1, len(position_speed)):
            curr_position, curr_speed = position_speed[idx]
            curr_time = (target - curr_position) / float(curr_speed)
            if curr_time > prev_time:
                prev_time = curr_time
                ret += 1

        return ret
