leetcode

0 class Solution {

1 public:

2 int carFleet(int target, vector<int> &position, vector<int> &speed) {

3 int n = position.size();

4 if (!n) return 0;

5 vector<pair<int, double>> vp(n + 1);

6

7 for (int i = 0; i < n; i++)

8 vp[i] = {position[i], (double)(target - position[i]) / speed[i]};

9 sort(vp.rbegin(), vp.rend());

10

11 int res = 0;

12 double ct = 0;

13 for (int i = 0; i < n; i++) {

14 auto [_, time] = vp[i];

15 if (time > ct) {

16 res++;

17 ct = time;

18 }

19 }

20 return res;

21 }

22 };

23

24 // Using map for the heavy lifting

25 class Solution {

26 public:

27 int carFleet(int target, vector<int> &position, vector<int> &speed) {

28 map<int, double> mp;

29

30 for (int i = 0; i < speed.size(); i++)

31 mp[-position[i]] = (double)(target - position[i]) / speed[i];

32

33 int res = 0;

34 double ct = 0;

35 for (auto [_, time] : mp) {

36 if (time > ct) {

37 res++;

38 ct = time;

39 }

40 }

41 return res;

42 }

43 };