[LeetCode]Car Fleet

题目链接

很直观的题目，我们只需要把所有的car按照离target的距离从小到大排列，然后依次扫过去看当前的车和前面的fleet的第一辆车能否在到达target之前相遇，可以的话这两车就merge到前面的fleet。否则这辆车就成为新的fleet的第一辆车。时间复杂度的话就是sorting的时间复杂度O(n * log n)，空间复杂度O(n)，代码如下：

这道题的follow up是在输入的基础上，如果有一辆跑的比其他车都快的车加入，可能在任何位置，输出结果集所有可能。其实仔细想一想不难理解，如果加在最前端，会多一个cluster，否则其前面的cluster的数量加一即可，也就是说所有其他cluster的数量都可以加一，输入所有结果即可。