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:

1. 0 <= N <= 10 ^ 4
2. 0 < target <= 10 ^ 6
3. 0 < speed[i] <= 10 ^ 6
4. 0 <= position[i] < target
5. All initial positions are different.

题目理解：

给定一系列车辆的位置和速度的集合，若后来车辆赶上前面的车辆，则合成为一个车队，问最终会形成多少个车队

解题思路：

首先按位置从近到远排列所有车辆，然后计算每一辆车到达终点的时间，如果后来的车辆行驶时间小于前面的车辆，那么说明它会追上前面的车辆并形成一个车队，若后来的车行驶时间大于前面的车辆，那么它将不会和前面的车辆形成车队，而会被它后面的车辆追上形成车队。根据以上分析，只需要计算行驶时间非递减的数目就行

代码如下：

class Solution {
	class Node implements Comparable<Node>{
		double position;
		int speed;
		public Node(int t, int s) {
			position = t;
			speed = s;
		}
		@Override
		public int compareTo(Node a) {
			// TODO Auto-generated method stub
			return (int)(a.position - this.position);
		}
	}
	
    public int carFleet(int target, int[] position, int[] speed) {
        int res = 0;
        double front;
        int len = position.length;
        if(len == 0)
        	return 0;
        List<Node> list = new ArrayList<Node>();
        for(int i = 0; i < len; i++) {
        	list.add(new Node(position[i], speed[i]));
        }
        Collections.sort(list);
        Node it = list.get(0);
        front = (target - it.position) / it.speed;
        for(int i = 1; i < len; i++) {
        	it = list.get(i);
        	double time = (target - it.position) / it.speed;
        	if(time > front) {
        		res++;
        		front = time;
        	}
        }
        return res + 1;
    }
}