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.

Difficulty: interview

Starter code:

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        

Solutions:
class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if not position:
            return 0
        
        posToSpeed = {position[i]: speed[i] for i in range(len(position))}
        position.sort()
        
        leaderTime = (target - position[-1]) / posToSpeed[position[-1]]
        currGroups = 1
        for i in range(len(position) - 2, -1, -1):
            currTime = (target - position[i]) / posToSpeed[position[i]]
            if currTime > leaderTime:
                currGroups += 1
                leaderTime = currTime
        
        return currGroups

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if(not position):
            return 0
        # def comp(a):
        #     return a[1],a[0]
        arr = list(zip(position,speed))
        arr.sort(reverse=True)
        ans=1
        reach=(target-arr[0][0])/arr[0][1]
        for p,s in arr[1:]:
            curr = (target-p)/s
            if(curr>reach):
                ans+=1
                reach=curr
        return ans
            
            
            
            
        


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed))
        times = [float(target - p) / 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)


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed))
        times = [float(target - p) / s for p, s in cars]
        ans = 0
        while len(times) > 1:
            lead = times.pop()
            if lead < times[-1]: ans += 1
            else: times[-1] = lead 
        return ans + bool(times)

class Solution:
    def check(self, target, p1, s1, p2, s2):
        if p1 == target and p2 == target:
            return True
        if p1 == target or p2 == target:
            return False
        d1 = float(target - p1)
        d2 = float(target - p2)
        if d1 / float(s1) <= d2 / float(s2):
            return True
        return False
    
    def solve(self, target, pos, speed):
        arr = []
        for i in range(len(pos)):
            p = pos[i]
            s = speed[i]
            arr.append((p, s))
        arr = sorted(arr)
        counter = 0
        ln = len(arr)
        i = ln-1
        # print(arr)
        while i >= 0:
            p2, s2 = arr[i]
            counter += 1
            j = i-1
            while j >= 0:
                p1, s1 = arr[j]
                if not self.check(target, p1, s1, p2, s2):
                    # print('not checked:', target, (p1, s1), (p2, s2))
                    break
                j-=1
            i = j
        return counter
    
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        return self.solve(target, position, speed)

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pos_speed = sorted(zip(position, speed))
        times = [(target-p)/s*1.0 for p, s in pos_speed]

        res = 0
        cur = 0
            
        for t in times[::-1]:
            if t > cur:
                res += 1
                cur = t
        
        return res

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        times = []
        for p in range(len(position)):
            times.append([(target - position[p])/speed[p], position[p]])
        
        times.sort()
        
        maxTime = 0
        res = 0
        #print(times)
        for t in range(len(times) - 1, -1, -1):
            if times[t][1] >= maxTime:
                res += 1
            maxTime = max(times[t][1], maxTime)
        
        return res
            
            


class Solution(object):
    def carFleet(self, target, position, speed):
        cars = sorted(zip(position, speed))
        times = [(target - p) / s for p, s in cars]
        ans = 0
        print(times)
        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)

class Solution:
    def carFleet(self, target, position, speed) -> int:
        ans,time=0, sorted([[position[i], (target-position[i])/speed[i]] for i in range(len(position))], reverse=True)+[[-1,float('inf')]]
        
        
        # print(time)
        for i in range(1,len(time)):
            if time[i-1][1]<time[i][1]:
                ans+=1
            else:
                time[i][1]=time[i-1][1]
                
        return ans


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = [(pos, speed) for pos, speed in zip(position, speed)]
        cars.sort()
        
        last_t = -1
        curr_t = 0
        fleets = 0
        
        for pos, speed in reversed(cars):
            curr_t = (target - pos) / speed
            
            if curr_t > last_t:
                fleets += 1
                last_t = curr_t
        
        return fleets

import collections
import numpy as np

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(range(len(position)), key=lambda i: position[i])
        def calc_finish_time(car):
            return (target - position[cars[car]]) / speed[cars[car]]
        fleets = 0
        next_finish_time = -1
        for car in range(len(cars)-1, -1, -1):
            finish_time = max(calc_finish_time(car), next_finish_time)
            if finish_time != next_finish_time:
                fleets += 1
            next_finish_time = finish_time                
        return fleets            

import collections
import numpy as np

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        tem=list(zip(position,speed))
        tem=sorted(tem, key=lambda x:x[0])
        count=0
        stack=[(target-tem[i][0])/tem[i][1] for i in range(len(tem))]
        stack=stack[::-1]
        cur=0
        for j in range(len(stack)):
            if stack[j]>cur:
                count+=1
                cur=stack[j]
        return count       

import collections
class Solution:
    def carFleet(self, D: int, P: List[int], S: List[int]) -> int:
        T = [(D-P[i])/S[i] for i in range(len(P))]
        sortedIdx = sorted(list(range(len(P))), key=lambda x: P[x])
        print(sortedIdx)
        stack = []
        for i in sortedIdx:
            while stack and T[stack[-1]] <= T[i]:
                stack.pop()
            stack.append(i)
            print(stack)
        return len(stack)


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
#         c=0
#         cnt=[]
#         for i in range(len(position)):
#             temp=[]
#             while(position[i]!=target):
#                 temp.append(position[i])
#                 position[i]=position[i]+speed[i]
#             temp.append(12)
#             cnt.append(temp)
#         for i in range(len(cnt)):
#             for j in range(i+1,len(cnt)):
#                 for k in cnt[i]:
#                     if k in cnt[j]:
#                         if(cnt[i].index(k)==cnt[j].index(k)):
#                             c=c+1
            
        
#         print(cnt)
            cars = sorted(zip(position, speed))
            print(cars)
            times = [float(target - p) / s for p, s in cars]
            print(times)
            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)

import collections
import numpy as np

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if len(position) < 1:
            return 0
        d = dict(zip(target - np.array(position), speed))
        ord_d = collections.OrderedDict(sorted(d.items()))
        count = 0
        r = -1
        for dist, speed in ord_d.items():
            t = dist / speed
            if t > r:
                count += 1
                r = t
        return count 

import collections
import numpy as np

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if len(position) < 1:
            return 0
        # d = dict(zip(target - np.array(position), speed))
        ord_d = collections.OrderedDict(sorted(dict(zip(target - np.array(position), speed)).items()))
        count = 0
        r = -1
        for dist, speed in ord_d.items():
            t = dist / speed
            if t > r:
                count += 1
                r = t
        return count 

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        times = []
        for p in range(len(position)):
            times.append([(target - position[p])/speed[p], position[p]])
        
        times.sort()
        
        maxTime = 0
        res = 0
        print(times)
        for t in range(len(times) - 1, -1, -1):
            if times[t][1] >= maxTime:
                res += 1
            maxTime = max(times[t][1], maxTime)
        
        return res
            
            


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        N = len(position)
        cars = sorted((s,p) for s,p in zip(speed, position))
        seen = set()
        res = 0
        # print(cars)
        for i in range(N):
            if i in seen: continue
            seen.add(i)
            res += 1
            
            for j in range(i+1, N):
                if j in seen or cars[j][0]==cars[i][0]: continue
                t = (cars[i][1]-cars[j][1])/(cars[j][0]-cars[i][0])
                if t<0 or t*cars[i][0]+cars[i][1]>target: continue
                seen.add(j)
                
        return res


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        ind = sorted(range(len(position)), key = lambda x: position[x])
        print(ind)
        r = len(speed) - 1
        fleet_num = 0
        while r >= 0:
            time = (target - position[ind[r]]) / speed[ind[r]]
            position[ind[r]] = target
            r = r-1
            while r >= 0 and position[ind[r]] + speed[ind[r]] * time >= target:
                position[ind[r]] = target
                r = r-1
            fleet_num += 1
            for i in range(r+1,-1):
                position[ind[i]] = min(position[ind[i]] + time * speed[ind[i]],position[ind[i+1]])
        return fleet_num

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if len(position) < 1:
            return 0
        acc = [(position[i], speed[i]) for i in range(len(position))]
        acc = sorted(acc, key=lambda x: x[0])
        
        fleets = 1
        predecessor_arrival = (target - acc[-1][0])/acc[-1][1]
        
        for i in range(len(acc) - 2, -1, -1):
            arrival = (target - acc[i][0])/acc[i][1]
            if arrival > predecessor_arrival:
                fleets += 1
                predecessor_arrival = arrival
        return fleets
        
# position: [10,8,0,5,3] -> [0,3,5,8,10]
# spee:     [2,4,1,1,3]  -> [1,3,1,4,2]

if True:
    print((Solution().carFleet(
        10,
        [0,4,2],
        [2,1,3]))) # 1
# [0,2,4]
# [2,3,1]
# [5,3,6]

# pos[i] + x1*speed[i] == 12
# pos[i+1] + x2*speed[i+1] == 12
# x1 = (12 - pos[i])/speed[i]
# x2 = (12 - pos[i+1])/speed[i+1]


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pos_speed = sorted(zip(position, speed))
        times = [float(target-p)/s for p, s in pos_speed]

        res = 0
        cur = 0
            
        for t in times[::-1]:
            if t > cur:
                res += 1
                cur = t
        
        return res

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        time = [(target - p) / s for p, s in sorted(zip(position, speed), key=lambda x: x[0])]
        fleets = 0
        last_arrive = 0
        for t in time[::-1]:
            if t > last_arrive:
                last_arrive = t
                fleets += 1
        return fleets

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        times = [(target - pos) / s for pos, s in sorted(zip(position, speed))]
        cur = ans = 0
        for time in times[::-1]:
            if time > cur:
                ans += 1
                cur = time
        return ans
        
    # start a new fleet when cur car's time to target is longer than the leader car of the cur fleet (i.e. cur car can't catch up with last fleet)
    # need to sort cars by position and start looping from the car closest to target becasue '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'. If we have cars A, B, C. time for A to reach target is shorter than B, then C. If we don't go from C to A, we don't know if there are three fleets or one. Going from C to A tells us it's one  


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if len(position) == 0:
            return 0
        time_required = []
        for i in range(len(position)):
            time_required.append((target-position[i])/speed[i])
        time_required = [x for _, x in sorted(zip(position, time_required), reverse=True)]
        print(time_required)
        count = 1
        previous_time = time_required[0]
        for i in range(1, len(time_required)):
            if time_required[i] > previous_time:
                count += 1
                previous_time = time_required[i]
        return count

class Solution(object):
    def carFleet(self, target, position, speed):
        if not position:   return 0
        cars = sorted(zip(position, speed))
        times = [float(target - p) / 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 + 1 


class Solution:
    def carFleet(self, target: int, P: List[int], S: List[int]) -> int:
        n = len(P)
        
        l = []
        for i in range(n):
            l.append((P[i],S[i]))
        
        l.sort(reverse=True)
        
        c = 0
        pt = -1
        for i,j in l:
            ct = (target - i) / j
            if ct > pt:
                c += 1
                pt = ct
                
        return c

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(list(zip(position,speed)))
        print(cars)
        times = [(target-p)/s for p,s in cars]
        
        ans = 0
        
        while (len(times)>1):# that means atleast 2 elements must be there cause we will pop one and then check one for comparing
            lead = times.pop()
            if lead<times[-1]:
                ans+=1
            else:
                times[-1]= lead
                
        return(ans+len(times)) # remaining car is fleet if it exists

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if len(position)==0:
            return 0
        pos_spd = sorted(zip(position,speed)) 
        position = [x for x,y in pos_spd]
        speed = [y for x,y in pos_spd]
        time = list([(target-x[0])/x[1] for x in pos_spd])
        idx = []
        count=1
        temp = time[-1]
        for val in time[::-1]:
            if val>temp: # cant catch the next one
                count+=1
                temp = val
        return count

            
                
            


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        stack = []
        for pos, vel in sorted(zip(position, speed))[::-1]:
            dist = target - pos
            if not stack:
                stack.append(dist / vel)
            elif dist / vel > stack[-1]:
                stack.append(dist / vel)
        return len(stack)
        
        


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        if not position:
            return 0
        
        posToSpeed = {position[i]: speed[i] for i in range(len(position))}
        position.sort()
        
        leaderTime = (target - position[-1]) / posToSpeed[position[-1]]
        currGroups = 1
        for i in range(len(position) - 2, -1, -1):
            currTime = (target - position[i]) / posToSpeed[position[i]]
            if currTime > leaderTime:
                currGroups += 1
                leaderTime = currTime
        
        return currGroups


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed))
        times = [(target-p) / s for (p, s) in cars]
        res = 0
        while len(times) >= 2:
            lead = times.pop()
            if times[-1] > lead:
                res += 1
            else:
                times[-1] = lead
            
        return res+ len(times)
                
        


class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # for each car:
        cars = []
        for i in range(len(speed)):
            cars.append([position[i], speed[i], (target - position[i]) / speed[i]])
        
        cars.sort(key=lambda x: x[0])
        #print(cars)
        
        maxs = []
        for car in cars[::-1]:
            if not maxs: maxs.insert(0, car[2])
            else: maxs.insert(0, max(maxs[0], car[2]))
        print(maxs)
        fleets = {}
        fleetCount = 0
        
        for i, car in enumerate(cars):
            inFleet = maxs[i+1] >= car[2] if i < len(cars)-1 else False
            if not inFleet:
                fleetCount+=1
        
        return fleetCount

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed))
        times = [float(target - p) / 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)

class Solution:
    def carFleet(self, target: int, p: List[int], s: List[int]) -> int:
        if not p:
            return 0
        l = [[p[i], s[i]] for i in range(len(p))]
        l.sort(reverse=True)
        x = l[0]
        res = 1
        
        for y in l[1:]:
            t = (target - y[0]) / y[1]
            if t > (target - x[0]) / x[1]:
                res += 1
                x = y
        return res

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        stack = []
        for pos, vel in sorted(zip(position, speed))[::-1]:
            dist = target - pos
            if not stack:
                stack.append(dist / vel)
            elif dist / vel > stack[-1]:
                stack.append(dist / vel)
        return len(stack)

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        # sort by starting position
        cars = sorted(zip(position, speed))
        times = [(target - p) / s for p, s, in cars]
        # count from back
        most = 0
        count = 0
        for i in range(len(times)-1 ,-1, -1):
            if times[i] > most:
                most = times[i]
                count += 1
                
        return count

class Solution(object):
    def carFleet(self, target, position, speed):
        cars = sorted(zip(position, speed))
        times = [float(target - p) / 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)