leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0853.cpp (1110B)

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 };