Bus and passenger solution approach


#1

It’s a simple problem which can be solved using sorting and stack data structure.

The approach is: Sort the array, and when type 0 passenger comes, assign the seats sequentially from the sorted array and also push the row into a stack, and when type 1 passenger comes, assign it the seat which is on the top of the stack and pop the stack once.

Time Complexity : O(nlogn)

Code
vector Solution::solve(vector &a, string b) {

    vector<pair<int,int>>v;
    int i,j,n=a.size();
    for(i=0;i<n;i++)
        v.push_back(make_pair(a[i],i+1));
    
    sort(v.begin(),v.end(),comp);
    
    vector<int>q;
    stack<pair<int,int>>s;
    // s.clear();
    j=0;
    for(i=0;i<b.length();i++)
    {
        if(b[i]=='0')
        {
            q.push_back(v[j].second);
            s.push(v[j]);
            j++;
        }
        else
        {
            int k = s.top().second;
            q.push_back(k);
            s.pop();
        }
    }
    return q;
}