PROBLEM LINK:
Author: Vallabh Deshpande
Tester: Mayuresh Patle
Editorialist: Vallabh Deshpande
DIFFICULTY:
EASY
PREREQUISITES:
Stack, Queue
PROBLEM:
Given the order of arrival of patients numbered 1 to N in a hospital, determine the order of them meeting the doctor such that:

The patient numbered X booked appointment before patient Y if X < Y.

If the patient who missed the appointment most recently has arrived, that patient should meet the doctor first otherwise the next available person should meet the doctor in order of booking.
QUICK EXPLANATION:
Use two queues for storing order of meeting and arrival and a stack for storing numbers of people who missed their appointment. If the topmost person in stack is available then that person will meet the doctor otherwise next person who arrives shall meet the doctor if that person hasnâ€™t missed the appointment yet.
EXPLANATION:
The problem requires us to fulfill the meeting of the person that booked appointment most recently but has missed his / her appointment and is currently available. Since we have to determine which people have missed their appointment and we require most recent among them we can use a stack to store them, and if the topmost numbered person is available we will keep fulfilling their appointment. Otherwise we store the order of booking and order of arrival in two separate queues and if any person who hasnâ€™t missed his /her appointment arrives we fulfill that personâ€™s appointment.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t){
ll n, x;
cin>>n;
stack< ll > missed;
queue< ll > arrival, booking;
bool available[n + 1] = {0};
for(ll i = 1; i <= n; ++i){
cin>>x;
arrival.push(x);
booking.push(i);
}
x = 0;
while(!booking.empty()  !missed.empty()){
while(!arrival.empty() && arrival.front() < x){
available[arrival.front()] = true;
arrival.pop();
if(!arrival.empty()) x = max(x, arrival.front());
}
if(!arrival.empty()){
x = max(x, arrival.front());
available[arrival.front()] = true;
}
while(!missed.empty() && available[missed.top()]){
cout<<missed.top()<<" ";
missed.pop();
}
while(!arrival.empty() && !booking.empty() && booking.front() != arrival.front()){
missed.push(booking.front());
booking.pop();
}
if(!booking.empty()){
cout<<booking.front()<<" ";
booking.pop();
}
if(!arrival.empty()){
arrival.pop();
}
}
cout<<"\n";
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
//freopen("inp.txt","r",stdin); freopen("out.txt","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T,n,curr,mx;
cin>>T;
while(T)
{
cin>>n;
stack <int> s;
vector <bool> in(n+1);
mx=0;
while(n)
{
cin>>curr;
if(mx<curr)
{
cout<<curr<<" ";
++mx;
while(mx<curr) s.push(mx++);
continue;
}
in[curr]=1;
while(!s.empty() and in[s.top()])
{
cout<<s.top()<<" ";
s.pop();
}
}
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
cout<<"\n";
}
return 0;
}