Gas Station

• Time : $O(nlogn)$
• Space : $O(n)$

#include <bits/stdc++.h>

int Solution::canCompleteCircuit(const vector<int> &A, const vector<int> &B) {
    int n = A.size();
    if(n == 1) return A[0] >= B[0] ? 0 : -1;
    vector<int> psum {0};
    for(int i = 0; i < A.size() * 2 - 1; i++) psum.push_back(psum[i] + A[i%n] - B[i%n]);
    priority_queue<int, vector<int>, greater<int>> q, exc;
    for(int i = 0; i < A.size() * 2 - 1; i++) {
        if(i >= n + 1) exc.push(psum[i-n-1]);
        while(!exc.empty() and exc.top() == q.top()) {
            exc.pop();
            q.pop();
        }
        q.push(psum[i]);
        if(i >= n and q.top() >= psum[i-n]) return i - n;
    }

    return -1;
}