leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0853.cpp (1110B)

      1 class Solution {
      2   public:
      3     int carFleet(int target, vector<int> &position, vector<int> &speed) {
      4         int n = position.size();
      5         if (!n) return 0;
      6         vector<pair<int, double>> vp(n + 1);
      7 
      8         for (int i = 0; i < n; i++)
      9             vp[i] = {position[i], (double)(target - position[i]) / speed[i]};
     10         sort(vp.rbegin(), vp.rend());
     11 
     12         int res = 0;
     13         double ct = 0;
     14         for (int i = 0; i < n; i++) {
     15             auto [_, time] = vp[i];
     16             if (time > ct) {
     17                 res++;
     18                 ct = time;
     19             }
     20         }
     21         return res;
     22     }
     23 };
     24 
     25 // Using map for the heavy lifting
     26 class Solution {
     27   public:
     28     int carFleet(int target, vector<int> &position, vector<int> &speed) {
     29         map<int, double> mp;
     30 
     31         for (int i = 0; i < speed.size(); i++)
     32             mp[-position[i]] = (double)(target - position[i]) / speed[i];
     33 
     34         int res = 0;
     35         double ct = 0;
     36         for (auto [_, time] : mp) {
     37             if (time > ct) {
     38                 res++;
     39                 ct = time;
     40             }
     41         }
     42         return res;
     43     }
     44 };