car_fleet

View Source

 1# @leet start
 2class Solution:
 3    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
 4        """
 5        To solve this question, we have to create a stack, finding
 6        out which items reach the same position before the target.
 7
 8        We know that any cars that have a position after a given car but a higher
 9        speed could meet before the target, merging to create a group.
10        Thus, we should figure out a way to distinguish which cars reach a target
11        before a given time.
12
13        To find out the number of car fleets, we need to sort the cars by
14        position, and then speed in reverse order.
15        We then iterate through the cars and figure out how many cars make a fleet.
16
17        For every car, we check the current fleet. If there isn't one, the current
18        car will become the fleet, and we move onto the next car.
19
20        If there is a fleet, we check to see if our current car will intersect
21        with the current fleet. If so, then we can add it to the current fleet,
22        and thus disregard it.
23
24        If the current car does not intersect with the current fleet, we start
25        a new one.
26
27        Finally, we return the number of fleets.
28        """
29        stack = []
30
31        for pos, s in sorted(zip(position, speed), reverse=True):
32            eta = (target - pos) / s
33            if not stack or eta > stack[-1]:
34                stack.append(eta)
35
36        return len(stack)
37
38
39# @leet end
40
41
42def test():
43    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
 5        """
 6        To solve this question, we have to create a stack, finding
 7        out which items reach the same position before the target.
 8
 9        We know that any cars that have a position after a given car but a higher
10        speed could meet before the target, merging to create a group.
11        Thus, we should figure out a way to distinguish which cars reach a target
12        before a given time.
13
14        To find out the number of car fleets, we need to sort the cars by
15        position, and then speed in reverse order.
16        We then iterate through the cars and figure out how many cars make a fleet.
17
18        For every car, we check the current fleet. If there isn't one, the current
19        car will become the fleet, and we move onto the next car.
20
21        If there is a fleet, we check to see if our current car will intersect
22        with the current fleet. If so, then we can add it to the current fleet,
23        and thus disregard it.
24
25        If the current car does not intersect with the current fleet, we start
26        a new one.
27
28        Finally, we return the number of fleets.
29        """
30        stack = []
31
32        for pos, s in sorted(zip(position, speed), reverse=True):
33            eta = (target - pos) / s
34            if not stack or eta > stack[-1]:
35                stack.append(eta)
36
37        return len(stack)

def carFleet(self, target: int, position: list[int], speed: list[int]) -> int: View Source

 4    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
 5        """
 6        To solve this question, we have to create a stack, finding
 7        out which items reach the same position before the target.
 8
 9        We know that any cars that have a position after a given car but a higher
10        speed could meet before the target, merging to create a group.
11        Thus, we should figure out a way to distinguish which cars reach a target
12        before a given time.
13
14        To find out the number of car fleets, we need to sort the cars by
15        position, and then speed in reverse order.
16        We then iterate through the cars and figure out how many cars make a fleet.
17
18        For every car, we check the current fleet. If there isn't one, the current
19        car will become the fleet, and we move onto the next car.
20
21        If there is a fleet, we check to see if our current car will intersect
22        with the current fleet. If so, then we can add it to the current fleet,
23        and thus disregard it.
24
25        If the current car does not intersect with the current fleet, we start
26        a new one.
27
28        Finally, we return the number of fleets.
29        """
30        stack = []
31
32        for pos, s in sorted(zip(position, speed), reverse=True):
33            eta = (target - pos) / s
34            if not stack or eta > stack[-1]:
35                stack.append(eta)
36
37        return len(stack)

To solve this question, we have to create a stack, finding out which items reach the same position before the target.

We know that any cars that have a position after a given car but a higher speed could meet before the target, merging to create a group. Thus, we should figure out a way to distinguish which cars reach a target before a given time.

To find out the number of car fleets, we need to sort the cars by position, and then speed in reverse order. We then iterate through the cars and figure out how many cars make a fleet.

For every car, we check the current fleet. If there isn't one, the current car will become the fleet, and we move onto the next car.

If there is a fleet, we check to see if our current car will intersect with the current fleet. If so, then we can add it to the current fleet, and thus disregard it.

If the current car does not intersect with the current fleet, we start a new one.

Finally, we return the number of fleets.

def test(): View Source

43def test():
44    assert 2 + 2 == 4