nikunjsoni

1776

Jul 26th, 2021
125
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<double> getCollisionTimes(vector<vector<int>>& A) {
  4.         int n = A.size();
  5.         vector<int> stack;
  6.         vector<double> res(n, -1);
  7.         for (int i = n - 1; i >= 0; --i) {
  8.             int p = A[i][0], s = A[i][1];
  9.             while (!stack.empty()) {
  10.                 int j = stack.back(), p2 = A[j][0], s2 = A[j][1];
  11.                 if (s <= s2 || 1.0 * (p2 - p) / (s - s2) >= res[j] && res[j] > 0)
  12.                     stack.pop_back();
  13.                 else
  14.                     break;
  15.             }
  16.             if (!stack.empty())
  17.                 res[i] = 1.0 * (A[stack.back()][0] - p) / (s - A[stack.back()][1]);
  18.             stack.push_back(i);
  19.         }
  20.         return res;
  21.     }
  22. };
RAW Paste Data