#
#
#
# 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.
import collections


class Solution(object):
    def carFleet(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """
        self.res = 0
        ps = [[p, s] for p, s in zip(position, speed)]
        self.drive(target, ps, 1)

        return self.res

    def drive(self, target, tuple, time):
        if not tuple or time == target + 1:
            return
        newT, arrived = [], []
        for t in tuple:
            d = t[0] + t[1]
            if d == target:
                arrived.append(t)
            else:
                found = False
                for k in newT:
                    if k[0] == d:
                        k[1] = min(d, k[1])
                        found = True
                if not found:
                    newT.append([d, t[1]])

        if arrived:
            self.res += 1
        self.drive(target, newT, time + 1)

    def carFleet2(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """
        self.res = 0
        ps = [[p, s] for p, s in zip(position, speed)]
        ps.sort()
        while ps:
            newT, arrived = [], []
            for t in ps:
                d = t[0] + t[1]
                if d >= target:
                    found = False
                    for k in arrived:
                        if k[0] == d:
                            found = True
                    if not found:
                        arrived.append([d, t[1]])
                else:
                    slow, near, deleted = float('inf'), float('inf'), []
                    for k in newT:
                        if k[0] >= d:
                            slow = min(slow, t[1], k[1])
                            near = min(near, d, k[0])
                            deleted.append(k)
                    if deleted:
                        for k in deleted:
                            newT.remove(k)
                        newT.append([near, slow])
                    else:
                        newT.append([d, t[1]])

            if arrived:
                self.res += len(arrived)
            ps = newT

        return self.res

    def carFleet(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """

        m = collections.defaultdict(int)

        for k, v in enumerate(position):
            m[v] = speed[k]

        position.sort()  # sort by position

        nSpeed, times = [0] * len(speed), [0] * len(speed)
        for k, v in enumerate(position):
            nSpeed[k] = m[v]
            times[k] = float(target - v) / m[v]

        res = collections.deque()
        # while i < len(times):
        #     while i + 1 < len(times) and times[i] <= times[i + 1]:
        #         i += 1
        #
        #     res, i = res + 1, i + 1

        for i in times:
            if not res or res[-1] > i:
                res.append(i)

        return len(res)

    def carFleet3(self, target, position, speed):
        cars = sorted(zip(position, speed))
        times = [(target - p) * 10000 / s for p, s in cars]
        ans = 0
        while len(times) > 1:
            lead = times.pop()
            if lead < times[-1]:
                ans += 1  # if lead arrives sooner, it can't be caught
            else:
                times[-1] = lead  # else, fleet arrives at later time 'lead'

        return ans + bool(times)  # remaining car is fleet (if it exists)

    def carFleet4(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """
        time = [float(target - p) / s for p, s in sorted(zip(position, speed))]
        res = cur = 0
        for t in time[::-1]:
            if t > cur:
                res += 1
                cur = t
        return res


if __name__ == '__main__':
    # print Solution().carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3])
    print Solution().carFleet4(660732, [620831, 145366, 229113, 144305, 382893, 514856, 171642, 87230, 409014, 65613],
                               [327716, 69772, 667805, 856849, 78755, 606982, 696937, 207697, 275337, 290550])
    print Solution().carFleet2(660732, [620831, 145366, 229113, 144305, 382893, 514856, 171642, 87230, 409014, 65613],
                               [327716, 69772, 667805, 856849, 78755, 606982, 696937, 207697, 275337, 290550])
    print Solution().carFleet(10, [8, 3, 7, 4, 6, 5], [4, 4, 4, 4, 4, 4])
    print Solution().carFleet2(10, [8, 3, 7, 4, 6, 5], [4, 4, 4, 4, 4, 4])
    print Solution().carFleet(20, [6, 2, 17], [3, 9, 2])
    print Solution().carFleet2(20, [6, 2, 17], [3, 9, 2])
    print Solution().carFleet(16, [11, 14, 13, 6], [2, 2, 6, 7])
    print Solution().carFleet2(16, [11, 14, 13, 6], [2, 2, 6, 7])
