Queue Time Stamp

Description:

给你两个independent queue，每个queue都存着timestamp，只能有getNext()来取queue里面的timestamp，每个timestamp只能被取一次，比较这两个queue里的timestamp，如果差值<1，print这两个timestamp。

Example:

例如：
Q1 0.2, 1.4, 3.0
Q2 1.0 1.1, 3.5
output: (0.2, 1.0), (1.4, 1.0), (0.2, 1.1), (1.4, 1.1), (3.0, 3.5)

Idea:

如果只有两个queue的话，从queue1里取数，然后keep一个deque buffer存queue2的数，每次如果deque前的数不符合条件就pop front，然后补充新的符合条件的数到deque后边。

如果N个queue，我想是还是deque buffer，然后先取最小的，然后所有符合条件的都进去，以从小到大顺序，然后把所有的pair都output（如果是自己queue里的不行）。然后再把deque front的拿出来，符合条件的进deque，然后output，继续这样。

Code:

#include <iostream>
#include <vector>
#include <climits>
#include <cassert>
#include <unordered_set>
#include <deque>
#include <cmath>

using namespace std;

vector<pair<double, double>> printTwoQueue(const vector<double>& q1, const vector<double>& q2){
    vector<pair<double, double>> result;

    deque<double> q2_buff;
    int q2_ind=0;

    for(auto q1_tim: q1){
        // 清理不符合条件的
        while(!q2_buff.empty() && abs(q1_tim-q2_buff.front())>1){
            q2_buff.pop_front();
        }
        // 符合条件的new element进去buffer
        while(q2_ind<q2.size() && abs(q1_tim-q2[q2_ind])<=1){
            q2_buff.push_back(q2[q2_ind]);
            q2_ind++;
        }
        for(auto e: q2_buff){
            result.push_back({q1_tim, e});
        }
    }

    return result;
}

int main(){
    vector<double> q1={0.2, 1.4, 3.0, 3.6, 3.9};
    vector<double> q2={1.0, 1.1, 3.5};

    vector<pair<double, double>> output = printTwoQueue(q1, q2);

    for(const auto & e: output){
        cout<<e.first<<' '<<e.second<<endl;
    }

}