#include<bits/stdc++.h>
using namespace std;


void fcfs(vector<int> arrival,vector<int> burst,bool flag)
{
    int start_time[105];
    int finish_time[105];
    int arri[105];
    int burst_time[105];

    int turn_time[105];
    int wait_time[105];

    int response_time[105];




    int n=arrival.size();


    vector <pair< int,pair<int,int> > > v;


    for(int i=1;i<=n;i++)
    {

        arri[i]=arrival[i-1];

        burst_time[i]=burst[i-1];

        v.push_back({arri[i],{i,burst_time[i]}});
    }

    sort(v.begin(),v.end());



    start_time[0]=v[0].first;
    finish_time[0]=v[0].first+v[0].second.second;

    int tot=0,idle=0;

    if(v[0].first>tot)
    {
        idle+=(v[0].first-tot);
        tot=v[0].first;
    }

    tot+=v[0].second.second;


    for(int i=1;i<n;i++)
    {
        int id=v[i].second.first;
        int arrival=v[i].first;

        if(arrival>tot)
        {
            idle+=(arrival-tot);
            tot=arrival;

        }

        int ex=v[i].second.second;

        finish_time[i]=max(finish_time[i-1],v[i].first)+ex;
        start_time[i]=max(finish_time[i-1],v[i].first);

        tot+=ex;
    }




    double tot_wait_time=0,tot_turn_time=0;

    for(int i=0;i<n;i++)
    {
        turn_time[i]=finish_time[i]-v[i].first;
        tot_turn_time+=finish_time[i]-v[i].first;
    }

    for(int i=0;i<n;i++)
    {
        wait_time[i]=turn_time[i]-v[i].second.second;
        tot_wait_time+=turn_time[i]-v[i].second.second;
    }

    for(int i=0;i<n;i++) response_time[i]=wait_time[i];

    if(flag)
    {


    cout<<"Gannt chart "<<endl;



    vector< pair<int,int> > ans;
    for(int i=0;i<n;i++)
    {
        ans.push_back({start_time[i],finish_time[i]});
    }

    int prev=0,idx=0;
    for(auto it:ans)
    {
        if(start_time[idx]!=prev)
        {
            cout<<prev<<" IDLE "<<start_time[idx];
            cout<<" P"<<v[idx].second.first<<" ";
        }
        else cout<<prev<<" P"<<v[idx].second.first<<" ";

        prev=finish_time[idx];
        idx++;
    }
    cout<<finish_time[idx-1]<<endl;



    for(int i=0;i<n;i++)
    {


        cout<<"Process: P"<<v[i].second.first<<" Finish time:  "<<finish_time[i]<<" ";
        cout<<"Response time:  "<<response_time[i]<<" ";
        cout<<"Waiting time:  "<<wait_time[i]<<" ";
        cout<<"Turnaround time:  "<<turn_time[i]<<" ";
        cout<<endl;

    }

    cout<<endl;

    }

    double s1=(double)tot_wait_time/n;

    double s2=(double)tot_turn_time/n;


    if(flag)
    {
        cout<<"Average waiting time :"<<s1<<endl;
        cout<<"Average turn arround time :"<<s2<<endl;
        cout<<"Total Idle time : "<<idle<<endl;
    }
    else
    {
       cout << "Algorithm: "<<1<<'\t'<<"Average Waiting Time: "<<s1;
       cout<<'\t'<<"Average Turnaround Time: "<<s2<< endl;
    }

}



void non_preemptive_sjf(vector<int>arrival,vector<int>burst,bool flag)
{
    long long int n=arrival.size();


    vector<pair<pair<long long int,long long int>, long long int> > v;
    long long int endTime[105];
    long long int response_time[105];

    for (long long int i = 0; i < n; i++)
    {

        long long int ar=arrival[i];

        long long int bt=burst[i];

        v.push_back({{ar, bt}, i+1});
    }
    sort(v.begin(), v.end());
    set<long long int> s;
    long long int start_time[105];
    start_time[0]=v[0].first.first;

    long long int idle=0;

    for (long long int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            endTime[i] = v[i].first.first + v[i].first.second;
            s.insert(v[i].second);
        }
        else
        {
            long long int mn = LLONG_MAX;
            long long int id = -1;

            for (long long int j = 0; j < n; j++)
            {
                if (v[j].first.first <= endTime[i - 1] && s.count(v[j].second) == 0 && v[j].first.second < mn)
                {
                    id = j;
                    mn = v[j].first.second;
                }
            }
            if (id != -1)
            {
                swap(v[id], v[i]);
                s.insert(v[i].second);
                endTime[i] = endTime[i - 1] + v[i].first.second;

                sort(v.begin()+ i+1, v.end());
            }
            else
            {
                endTime[i] = v[i].first.first + v[i].first.second;
                s.insert(v[i].second);
            }
            start_time[i]=max(endTime[i-1],v[i].first.first);
        }
    }


    long long int turnAround[105];
    long long int waitingTime[105];
    double tot_turn_time = 0;
    double tot_wait_time = 0;

    for (long long int i = 0; i < n; i++)
    {
        turnAround[i] = endTime[i] - v[i].first.first;
        waitingTime[i] = turnAround[i] - v[i].first.second;
        tot_turn_time += turnAround[i];
        tot_wait_time += waitingTime[i];
    }


    for(int i=0;i<n;i++) response_time[i]=waitingTime[i];

    double s1=(double)tot_wait_time/n;

    double s2=(double)tot_turn_time/n;

    if(flag)
    {

    cout<<"Gantt Chart:"<<endl;

    vector<pair<long long int,long long int> > ans;
    for(long long int i=0;i<n;i++)
    {
        ans.push_back({start_time[i],endTime[i]});
    }

    long long int prev=0,idx=0;
    for(auto it:ans)
    {
        if(start_time[idx]!=prev)
        {
            cout<<prev<<" IDLE "<<start_time[idx];
            cout<<" P"<<v[idx].second<<" ";
            idle+=(start_time[idx]-prev);

        }
        else cout<<prev<<" P"<<v[idx].second<<" ";

        prev=endTime[idx];
        idx++;
    }
    cout<<endTime[idx-1]<<endl;

    for(int i=0;i<n;i++)
    {

        cout<<"Process: P"<<v[i].second<<" Finish time:  "<<endTime[i]<<" ";
        cout<<"Response time:  "<<response_time[i]<<" ";
        cout<<"Waiting time:  "<<waitingTime[i]<<" ";
        cout<<"Turnaround time:  "<<turnAround[i]<<" ";
        cout<<endl;

    }

    cout<<endl;

    }

    if(flag)
    {
        cout<<"Average waiting time :"<<s1<<endl;
        cout<<"Average turn arround time :"<<s2<<endl;
        cout<<"Total Idle time : "<<idle<<endl;
    }
    else
    {
       cout << "Algorithm: "<<2<<'\t'<<"Average Waiting Time: "<<s1;
       cout<<'\t'<<"Average Turnaround Time: "<<s2<< endl;
    }
}



///map<int,int>mp;
typedef pair<int,pair<int,int>>pi;
///vector<pair<int,pair<int,int>>>v;

void preemptive_sjf(vector<int>arrival,vector<int>burst,bool f)
{
   vector<pair<int,pair<int,int>>>v;
   map<int,int>mp;

    int n=arrival.size();



    int finish_t[100];
    int flag[100];
    int resp_t[100];
    int burst_time[102];
    int  arri_time[102];
     vector<pair<int,int>>gantchart;
     memset(flag,0,sizeof(flag));
     memset(resp_t,0,sizeof(resp_t));
     priority_queue<pi,vector<pi>,greater<pi>>q;


     for(int i=1;i<=n;i++)
     {

        arri_time[i]=arrival[i-1];

        burst_time[i]=burst[i-1];
        v.push_back({arri_time[i],{burst_time[i],i}});

        ///flag[i-1]=0;

    }

    sort(v.begin(),v.end());

    q.push({v[0].second.first,{v[0].first,v[0].second.second}});
    int cur=0;
    cur=v[0].first;

    flag[0]=1;
    int total_idle=cur;
    if(cur!=0){
        mp[0]=cur;
    }
    int cnt=1;
    while(!q.empty())
        {
        int y=q.top().second.second;
        int x=q.top().first;
        int ar=q.top().second.first;
        q.pop();

        if(x>=1){
            if(!resp_t[y]){
                resp_t[y]=cur;
            }
            if(cnt<n)
            {
            cur++;
            finish_t[y]=cur;
            x--;
            gantchart.push_back({y,cur});
            }
            else{
            finish_t[y]=cur+x;
            cur+=x;
            x=0;
            gantchart.push_back({y,cur});
            }
        }
        for(int i=0;i<n;i++){

            if(v[i].first<=cur && flag[i]==0){
                  q.push({v[i].second.first,{v[i].first,v[i].second.second}});
                 cnt++;
                 flag[i]=1;
            }
        }
        if(x>0){
           q.push({x,{ar,y}});
        }
        if(q.empty() and cnt<n )
        {
            for(int i=0;i<n;i++){
                if(flag[i]==0){
                    q.push({v[i].second.first,{v[i].first,v[i].second.second}});
                   total_idle+= v[i].first-cur;
                   mp[cur]=v[i].first;
                   cur=v[i].first;
                   flag[i]=1;
                   cnt++;
                   break;
                }
            }
        }
    }

    if(f)
    {

    cout<<"Gantt Chart: :";
    cout<<0<<" ";
    if(mp[0]!=0)cout<<"Idle "<<mp[0]<<" ";
    for(auto u:gantchart)
    {
        cout<<"P"<<u.first<<" "<<u.second<<" ";
        if(mp[u.second]!=0){
            cout<<"Idle "<<mp[u.second]<<" ";

        }

    }
    cout<<endl;
    }

    int turnAround[101];
    int waitingTime[101];
    double avgTurnAround = 0;
    double avgwaitingTime = 0;
    for (int i = 1; i <= n; i++)
    {
        resp_t[i]=resp_t[i]-arri_time[i];
        turnAround[i] = finish_t[i] - arri_time[i];
        waitingTime[i] = turnAround[i] - burst_time[i];
        ///cout<<"Turn "<<turnAround[i]<<" WAIT "<<waitingTime[i]<<endl;
        avgTurnAround += turnAround[i];
        avgwaitingTime += waitingTime[i];
    }

    double s2=(double)avgTurnAround / n ;
    double s1=(double)avgwaitingTime / n ;

    if(f)
    {

    for (int i = 1; i <=n; i++)
    {
        cout<<"Process: p"<<i<<" Finish Time: "<<finish_t[i]<<" Response Time: "<<resp_t[i]<<" Waiting Time: "<<waitingTime[i] ;
        cout<<" Turnaround Time: "<<turnAround[i]<<endl;
    }

    cout << "Average waiting time: " <<s1<< endl;
     cout << "Average turnaround time: " <<s2<< endl;

    cout<<"Total_Idle :"<<total_idle<<endl;

    }
    else
    {
        cout << "Algorithm: "<<3<<'\t'<<"Average Waiting Time: "<<s1;
       cout<<'\t'<<"Average Turnaround Time: "<<s2<< endl;
    }
}



struct job
{
    int PID, ART, BT, WT = 0, TAT =0, STT =-2, ENT = -2, RT, PRT, RSP;
    bool f=0;
};
void sort_PID(int n, struct job (& b)[100])
{
    int i, j, t;
    for(i=0; i<n-1; i++)
    {
        t=i;
        for(j=i+1; j<n; j++)
        {
            if(b[j].PID<b[t].PID)
                t=j;
        }
        swap(b[i], b[t]);
    }
}

void sort_ART(int n, struct job (& b)[100])
{
    int i, j, t;
    for(i=0; i<n-1; i++)
    {
        t=i;
        for(j=i+1; j<n; j++)
        {
            if(b[j].ART < b[t].ART)
                t=j;
        }
        swap(b[i], b[t]);
    }
}


int preemp_next_job(int CT,int n, struct job (& b)[100])
{
    if(b[0].ART>CT)
    return -1;
    int i=0;
    int tmp = -1;
    while(b[i].ART<=CT)
    {
        if(b[i].RT != 0 && tmp == -1)
        {
            tmp = i;
        }

        else if(b[i].PRT < b[tmp].PRT && b[i].RT!=0) //Higher number higher priority(>)//Higher number lower priority (<)
            tmp = i;
        i++;
        if(i>n)
            break;
    }
        return tmp;
}

int nonpreemp_next_job(int CT,int n, struct job (& a)[100])
{
    if(a[0].ART>CT)
    return -1;
    int i=0;
    int tmp = -1;
    while(a[i].ART<=CT)
    {
        if(a[i].RT != 0 && tmp == -1)
        {
            tmp = i;
        }
        else if(a[i].PRT < a[tmp].PRT && a[i].RT!=0) //Higher number higher priority(>)//Higher number lower priority (<)
            tmp = i;
        i++;
        if(i>n)
            break;
    }
        return tmp;

}
void non_preemptive_priority(vector<int> arrival,vector<int> burst,vector<int> priority,bool flag)
{
    job a[100];
    vector <int> GT;
    int n=arrival.size(), i, j, T=0;


    for(i=0; i<n; i++)
    {
             a[i].PID=i+1;

             a[i].ART=arrival[i];

             a[i].BT=burst[i];
             a[i].RT = a[i].BT;

              a[i].PRT=priority[i];


    }
//Sort according to Arrival time
    sort_ART(n,a);
//gantt chart creation

   int CT = 0, cnt = 0;
    while(1)
    {
            i = nonpreemp_next_job(CT,n, a);
            if(i!=-1)
            {
                while(a[i].RT!=0)
                {
                    GT.push_back(i);
                    a[i].RT--;
                    CT++;
                }
                    cnt++;
            }
            else
            {
                CT++;
                GT.push_back(-1);
            }
        if(cnt==n)
            break;
    }
   // Start time and total idle time using Gantt chart
   int TOTAT_IDLE=0;
    for(i=0; i<GT.size(); i++)
    {
        if(GT[i]!=-1 && a[GT[i]].STT==-2)
        {
            a[GT[i]].STT = i;
        }
        if(GT[i]==-1)
            TOTAT_IDLE++;
    }
    // END time calculation using Gantt chart
    for(i=GT.size()-1; i>=0; i--)
    {
        if(GT[i]!=-1 && a[GT[i]].ENT==-2)
            a[GT[i]].ENT = i+1;
    }
    // other values using gantt chart
    for(i=0; i<n; i++)
    {
        a[i].TAT = a[i].ENT - a[i].ART;
        a[i].WT = a[i].TAT - a[i].BT;
        a[i].RSP = a[i].STT - a[i].ART;

    }

    //gantt chart print

    if(flag)
    {

    cout << "Gantt Chart" << endl << endl;

    int prev = -2;
    for(i=0; i<GT.size(); i++)
    {
        if(GT[i]!=prev)
        {
            if(GT[i]!=-1)
            cout << i << "  p" << a[GT[i]].PID << "  ";
            else
            cout << i << "  idle " ;
        }
        prev=GT[i];
    }
    cout << i;

    }

    cout<<endl;

    //Output print
    //Sort according to Process ID
    sort_PID(n, a);

    int TOTAL_TAT=0, TOTAL_WT=0;
    ///cout << "PID\tArrival Time\tStart Time\tEnd Time\tTurn Around Time\tWaiting time\tResponse Time"<<endl;
    for(i=0; i<n; i++)
    {
        /*cout << a[i].PID <<"\t";
        cout << a[i].ART <<"\t\t";
        cout << a[i].STT <<"\t\t";
        cout << a[i].ENT <<"\t\t";
        cout << a[i].TAT <<"\t\t\t";
        cout << a[i].WT  <<"\t\t";
        cout << a[i].RSP <<"\n";*/

        TOTAL_TAT += a[i].TAT;
        TOTAL_WT += a[i].WT;
    }

    double s2=double(TOTAL_TAT)/n;
    double s1=double(TOTAL_WT)/n;




    if(flag)
    {

    for (int i = 0; i <n; i++)
    {
        cout<<"Process: p"<<a[i].PID<<" Finish Time: "<<a[i].ENT<<" Response Time: "<<a[i].RSP<<" Waiting Time: "<<a[i].WT ;
        cout<<" Turnaround Time: "<<a[i].TAT<<endl;
    }

     cout << "Average waiting time: " <<s1<< endl;
     cout << "Average turnaround time: " <<s2<< endl;

    cout<<"Total_Idle :"<<TOTAT_IDLE<<endl;

    }
    else
    {
        cout << "Algorithm: "<<4<<'\t'<<"Average Waiting Time: "<<s1;
       cout<<'\t'<<"Average Turnaround Time: "<<s2<< endl;
    }


}

void preemptive_priority(vector<int> arrival,vector<int> burst,vector<int> priority,bool flag)
{
    job b[100];

    vector <int> GT;
    int n=arrival.size(), i, j, T=0;


    for(i=0; i<n; i++)
    {
            b[i].PID=i+1;

            b[i].ART=arrival[i];

             b[i].BT=burst[i];
             b[i].RT = b[i].BT;

            b[i].PRT=priority[i];

    }
    sort_ART(n, b);

//gantt chart creation
   int CT = 0, cnt = 0;
    while(1)
    {
        i = preemp_next_job(CT,n, b);
        if(i!=-1)
        {
            GT.push_back(i);
            b[i].RT--;
            if(b[i].RT == 0)
                cnt++;
            CT++;
        }
        else
        {
            CT++;
            GT.push_back(-1);
        }
        if(cnt==n)
            break;
    }
   // Start time and total idle time using Gantt Chart
   int TOTAT_IDLE=0;
    for(i=0; i<GT.size(); i++)
    {
        if(GT[i]!=-1 && b[GT[i]].STT==-2)
        {
            b[GT[i]].STT = i;
        }
        if(GT[i]==-1)
            TOTAT_IDLE++;
    }
    // END time using gantt chart
    for(i=GT.size()-1; i>=0; i--)
    {
        if(GT[i]!=-1 && b[GT[i]].ENT==-2)
            b[GT[i]].ENT = i+1;
    }
    // other values using gantt chart
    for(i=0; i<n; i++)
    {
        b[i].TAT = b[i].ENT - b[i].ART;
        b[i].WT = b[i].TAT - b[i].BT;
        b[i].RSP = b[i].STT - b[i].ART;
    }

    //gantt chart print

    if(flag)
    {


    cout << "Gantt Chart" << endl << endl;
    int prev = -2;
    for(i=0; i<GT.size(); i++)
    {
        if(GT[i]!=prev)
        {
            if(GT[i]!=-1)
            cout << i << "  p" << b[GT[i]].PID << "  ";
            else
            cout << i << "  idle  " ;
        }
        prev=GT[i];
    }
    cout << i;

    }

    //Output print
    sort_PID(n, b);

    int TOTAL_TAT=0, TOTAL_WT=0;
   // cout << "PID\tArrival Time\tStart Time\tEnd Time\tTurn Around Time\tWaiting time\tResponse Time"<<endl;

    for(i=0; i<n; i++)
    {
        /*cout << b[i].PID <<"\t";
        cout << b[i].ART <<"\t\t";
        cout << b[i].STT <<"\t\t";
        cout << b[i].ENT <<"\t\t";
        cout << b[i].TAT <<"\t\t\t";
        cout << b[i].WT  <<"\t\t";
        cout << b[i].RSP <<"\n";*/

        TOTAL_TAT += b[i].TAT;
        TOTAL_WT += b[i].WT;
    }

    double s1=double(TOTAL_WT)/n;
    double s2=double(TOTAL_TAT)/n;

    if(flag)
    {

    for (int i = 0; i <n; i++)
    {
        cout<<"Process: p"<<b[i].PID<<" Finish Time: "<<b[i].ENT<<" Response Time: "<<b[i].RSP<<" Waiting Time: "<<b[i].WT ;
        cout<<" Turnaround Time: "<<b[i].TAT<<endl;
    }

     cout << "Average waiting time: " <<s1<< endl;
     cout << "Average turnaround time: " <<s2<< endl;

    cout<<"Total_Idle :"<<TOTAT_IDLE<<endl;

    }
    else
    {
        cout << "Algorithm: "<<5<<'\t'<<"Average Waiting Time: "<<s1;
       cout<<'\t'<<"Average Turnaround Time: "<<s2<< endl;
    }

}







void round_robin(vector<int>ar,vector<int>bt,int tq,bool f)
{
    int arrival[5000],burst[5000],end_time[5000],id[5000],flag[5000],res_time[5000];
    int n=ar.size();

    double turn_time[5000],wait_time[5000];



     vector< pair<int,pair<int,int>> >v;

     int context=0;


    for(int i=1;i<=n;i++)
    {
        int x,y;
        x=ar[i-1];
        arrival[i]=x;


        y=bt[i-1];
        burst[i]=y;

        res_time[i]=-1;

        flag[i-1]=0;

        v.push_back({x,{i,y}});

    }

    int TQ=tq;


    sort(v.begin(),v.end());


    map<int,int> gap;  ///saves { idle time start, idle itme end }
    vector<pair<int,int> > g;  ///saves the { pid, end time }

    queue< pair<int,int> > q;

    q.push({v[0].second.first,v[0].second.second});   ///id burst time
    flag[0]=1;

    int cur_time=0,tot_idle=0;

    cur_time=v[0].first;

    ///idle in the start

    if(cur_time!=0)
    {
        tot_idle+=cur_time;
        gap[0]=cur_time;
    }

    int completed=0;

    while(!q.empty() and completed!=n)
    {

        int id=q.front().first;
        int bur=q.front().second;
        q.pop();

        ///cout<<"ID "<<id<<" BUR "<<bur<<endl;

        context++;




        if(res_time[id]!=0) res_time[id]=cur_time;


        int rem;
        if(TQ>=bur)
        {
            cur_time+=bur;
           /// burst2[pt]=0;
           end_time[id]=cur_time;
           rem=0;
           completed++;

        }
        else
        {
            cur_time+=TQ;
           /// burst2[pt]-=TQ;
           rem=bur-TQ;
        }

        g.push_back({id,cur_time});


        for(int i=0;i<n;i++)
        {
            if(v[i].first<=cur_time and flag[i]==0)
            {
                q.push({v[i].second.first,v[i].second.second});

                flag[i]=1;
            }
        }

        if(rem) q.push({id,rem});

        ///idle time in middle

        if(q.empty())
        {
            if(completed!=n)
            {
                for(int i=0;i<n;i++)
                {
                    if(flag[i]==0)
                    {
                        q.push({v[i].second.first,v[i].second.second});
                        tot_idle+=(v[i].first-cur_time);

                        gap[cur_time]=v[i].first;

                        cur_time=v[i].first;
                        flag[i]=1;

                        break;
                    }
                }

            }

        }



    }


    for(int i=1;i<=n;i++)
    {
        int x=res_time[i];
        res_time[i]=x-arrival[i];
    }

    double tot_turn_time=0;
    double tot_wait_time=0;

    for(int i=1;i<=n;i++)
    {
        double x=end_time[i]-arrival[i];
        turn_time[i]=x;
        tot_turn_time+=x;
    }

    for(int i=1;i<=n;i++)
    {
        double x=turn_time[i]-burst[i];
        wait_time[i]=x;
        tot_wait_time+=x;
    }



    if(f)
    {

    cout<<"Gantt Chart: :";
    cout<<0<<" ";

    if(gap[0]!=0)cout<<"Idle "<<gap[0]<<" ";

    for(auto it:g)
    {
        int id=it.first;
        int ed=it.second;

        cout<<"P"<<id<<" "<<ed<<" ";

        if(gap[ed]!=0)
        {
            cout<<"Idle "<<gap[ed]<<" ";
        }
    }
    cout<<endl;

    }

    double s1=tot_wait_time/n;
    double s2=tot_turn_time/n;

    if(f)
    {

    for(int i=1;i<=n;i++)
    {
        cout<<"Process: p"<<i<<" Finish Time: "<<end_time[i]<<" Response Time: "<<res_time[i]<<" Waiting Time: "<<wait_time[i] ;
        cout<<" Turnaround Time: "<<turn_time[i]<<endl;
        cout<<endl;
    }
    cout<<endl;



    cout << "Average waiting time: " <<s1<< endl;
    cout << "Average turnaround time: " <<s2<< endl;

    cout<<"Total_Idle :"<<tot_idle<<endl;

    }
    else
    {
        cout << "Algorithm: "<<6<<'\t'<<"Average Waiting Time: "<<s1;
       cout<<'\t'<<"Average Turnaround Time: "<<s2<< endl;
    }

    context--;

    cout<<"CONTEXT SWITCH "<<context<<endl;

}



queue<int> readyq;

int finding_time_quantum()
{

    double sm=0,avg,sz=readyq.size();

    vector<int>rem_time;


    while(!readyq.empty())
    {
        int x=readyq.front();
        readyq.pop();

        rem_time.push_back(x);

        sm=(double)sm+x;


    }


    avg=sm/(sz);

    int t=ceil(avg);

    for(auto it:rem_time)
    {
       readyq.push(it);

    }

    return t;

}

void proposed_algo(vector<int>ar,vector<int>bt,vector<int>priority,bool f)
{
    while(!readyq.empty()) readyq.pop();

    int arrival[5000],burst[5000],end_time[5000],id[5000],flag[5000],res_time[5000],prio[5000];
    int n=ar.size();

    double turn_time[5000],wait_time[5000];

    vector< pair< int,pair <int,pair<int,int> > > >v;
    int completed=0;
    int context=0;


    for(int i=1;i<=n;i++)
    {
        int x,y,p;

        x=ar[i-1];
        arrival[i]=x;


        y=bt[i-1];
        burst[i]=y;


        p=priority[i-1];
        prio[i]=p;

        res_time[i]=-1;

        flag[i-1]=0;



        v.push_back({arrival[i],{prio[i],{burst[i],i}}});

    }

    int TQ;


    sort(v.begin(),v.end());
    ///for(auto it:v) cout<<it.first<<" ";
   /// cout<<endl;


    map<int,int> gap;  ///saves { idle time start, idle itme end }

    vector<pair<int,int> > g;  ///saves the { pid, end time }

    queue< pair<int,int> > q;



    q.push({v[0].second.second.second,v[0].second.second.first});   ///id burst time
    flag[0]=1;



    readyq.push(v[0].second.second.first);



    int cur_time=0,tot_idle=0;

    cur_time=v[0].first;

    ///idle in the start

    if(cur_time!=0)
    {
        tot_idle+=cur_time;
        gap[0]=cur_time;
    }



    while(!q.empty() and completed!=n)
    {

        int id=q.front().first;
        int bur=q.front().second;
        q.pop();

        context++;



        ///cout<<"ID "<<id<<" bur "<<bur<<endl;



        TQ=finding_time_quantum();

        ///cout<<"TQ "<<TQ<<endl;

        readyq.pop();



        if(res_time[id]==-1) res_time[id]=cur_time;


        int rem;
        if(TQ>=bur)
        {
           cur_time+=bur;

           end_time[id]=cur_time;
           rem=0;
           completed++;



        }
        else
        {
            cur_time+=TQ;
            rem=bur-TQ;


        }

        g.push_back({id,cur_time});



        vector< pair< int,pair <int,pair<int,int> > > >rv;  /// p, burst , arri ,id


        for(int i=0;i<n;i++)
        {
            if(v[i].first<=cur_time and flag[i]==0)
            {
                ///cout<<""

                ///q.push({v[i].second.second.second,v[i].second.second.first});
                rv.push_back({v[i].second.first,{v[i].second.second.first,{v[i].first,v[i].second.second.second}}});

                flag[i]=1;

                ///readyq.push(v[i].second.second.first);
            }
        }
        sort(rv.begin(),rv.end());

        for(auto it:rv)
        {
            q.push({it.second.second.second,it.second.first});
            readyq.push(it.second.first);
        }



       /// cout<<"ID2 "<<id<<" bur "<<rem<<endl;

        if(rem!=0)
        {
            q.push({id,rem});

            readyq.push(rem);

        }




        ///idle time in middle

        if(q.empty())
        {
            if(completed!=n)
            {
                for(int i=0;i<n;i++)
                {
                    if(flag[i]==0)
                    {
                        ///cout<<"I "<<i<<endl;

                       q.push({v[i].second.second.second,v[i].second.second.first});
                        tot_idle+=(v[i].first-cur_time);

                        gap[cur_time]=v[i].first;

                        cur_time=v[i].first;
                        flag[i]=1;

                        readyq.push(v[i].second.second.first);

                        break;
                    }
                }

            }

        }







    }


    for(int i=1;i<=n;i++)
    {
        int x=res_time[i];
        res_time[i]=x-arrival[i];
    }

    double tot_turn_time=0;
    double tot_wait_time=0;

    for(int i=1;i<=n;i++)
    {
        double x=end_time[i]-arrival[i];
        turn_time[i]=x;
        tot_turn_time+=x;
    }

    for(int i=1;i<=n;i++)
    {
        double x=turn_time[i]-burst[i];
        wait_time[i]=x;
        tot_wait_time+=x;
    }



    if(f)
    {


    cout<<"Gantt Chart: :";
    cout<<0<<" ";

    if(gap[0]!=0)cout<<"Idle "<<gap[0]<<" ";

    for(auto it:g)
    {
        int id=it.first;
        int ed=it.second;

        cout<<"P"<<id<<" "<<ed<<" ";

        if(gap[ed]!=0)
        {
            cout<<"Idle "<<gap[ed]<<" ";
        }
    }
    cout<<endl;

    }

    double s1=tot_wait_time/n;
    double s2=tot_turn_time/n;

    if(f)
    {

    for(int i=1;i<=n;i++)
    {
        cout<<"Process: p"<<i<<" Finish Time: "<<end_time[i]<<" Response Time: "<<res_time[i]<<" Waiting Time: "<<wait_time[i] ;
        cout<<" Turnaround Time: "<<turn_time[i]<<endl;
        cout<<endl;
    }
    cout<<endl;



    cout << "Average waiting time: " <<s1<< endl;
    cout << "Average turnaround time: " <<s2<< endl;

    cout<<"Total_Idle :"<<tot_idle<<endl;

    }
    else
    {
         ///cout << "Average waiting time: " <<s1<< endl;
       ///cout << "Average turnaround time: " <<s2<< endl;
        cout << "Algorithm: "<<7<<'\t'<<"Average Waiting Time: "<<s1;
       cout<<'\t'<<"Average Turnaround Time: "<<s2<< endl;
    }


    context--;
    cout<<"CONTEXT "<<context<<endl;



}


void compare_all(vector<int> arrival,vector<int> burst,vector<int> priority,int tq)
{
    fcfs(arrival,burst,0);
    non_preemptive_sjf(arrival,burst,0);
    preemptive_sjf(arrival,burst,0);

    non_preemptive_priority(arrival,burst,priority,0);
    preemptive_priority(arrival,burst,priority,0);


    round_robin(arrival,burst,tq,0);
    proposed_algo(arrival,burst,priority,0);
}


int main()
{
    while(1)
    {


        cout<<"1: FCFS"<<endl;
        cout<<"2: Non-Preemptive-SJF"<<endl;
        cout<<"3: Preemptive-SJF"<<endl;
        cout<<"4: Non-Preemptive-Priority"<<endl;
        cout<<"5: Preemptive-Priority"<<endl;
        cout<<"6: Round-Robin"<<endl;
        cout<<"7: Our-Proposed-Algorithm"<<endl;
        cout<<"8: Compare-All"<<endl;
        cout<<"9: Exit "<<endl;


        cout<<"Input your Choice: ";

        int choice;cin>>choice;
        if(choice==9) return 0;


        cout<<"Number of Process,n: ";
        int n;cin>>n;

        cout<<endl;

        int tq;

        vector<int> arrival,burst,priority;

        if(choice>=1 and choice<=3)
        {

        for(int i=1;i<=n;i++)
        {
            int a,b;
            cout<<"Enter the arrival time of P"<<i<< ": ";
            cin>>a;
            arrival.push_back(a);

            cout<<"Enter the burst time of P" <<i<< ": ";
            cin>>b;
            burst.push_back(b);

            cout << endl;
        }

        }
        else if(choice>=4 and choice<=5)
        {
            for(int i=1;i<=n;i++)
            {
            int a,b,p;
            cout<<"Enter the arrival time of P"<<i<< ": ";
            cin>>a;
            arrival.push_back(a);

            cout<<"Enter the burst time of P" <<i<< ": ";
            cin>>b;
            burst.push_back(b);


            cout << "Enter Priority of p" << i << ": " ;
            cin>>p;
            priority.push_back(p);

            cout << endl;
           }
        }
        else if(choice==6)
        {
            for(int i=1;i<=n;i++)
            {
            int a,b;
            cout<<"Enter the arrival time of P"<<i<< ": ";
            cin>>a;
            arrival.push_back(a);

            cout<<"Enter the burst time of P" <<i<< ": ";
            cin>>b;
            burst.push_back(b);

            cout << endl;
           }

           cout<<"Enter the time Quantum : ";
           cin>>tq;
           cout<<endl;

        }
        else if(choice==7)
        {
            for(int i=1;i<=n;i++)
            {
            int a,b,p;
            cout<<"Enter the arrival time of P"<<i<< ": ";
            cin>>a;
            arrival.push_back(a);

            cout<<"Enter the burst time of P" <<i<< ": ";
            cin>>b;
            burst.push_back(b);


            cout << "Enter Priority of p" << i << ": " ;
            cin>>p;
            priority.push_back(p);

            cout << endl;
           }
        }
        else if(choice==8)
        {
            for(int i=1;i<=n;i++)
            {
            int a,b,p;
            cout<<"Enter the arrival time of P"<<i<< ": ";
            cin>>a;
            arrival.push_back(a);

            cout<<"Enter the burst time of P" <<i<< ": ";
            cin>>b;
            burst.push_back(b);


            cout << "Enter Priority of p" << i << ": " ;
            cin>>p;
            priority.push_back(p);

            cout << endl;
           }

           cout<<"Enter the time Quantum : ";
           cin>>tq;
           cout<<endl;
        }




        if(choice==1)
        {
            fcfs(arrival,burst,1);
        }
        else if(choice==2)
        {
            non_preemptive_sjf(arrival,burst,1);
        }

        else if(choice==3)
        {
            preemptive_sjf(arrival,burst,1);
        }
        else if(choice==4)
        {
            non_preemptive_priority(arrival,burst,priority,1);
        }
        else if(choice==5)
        {
            preemptive_priority(arrival,burst,priority,1);
        }
        else if(choice==6)
        {
            round_robin(arrival,burst,tq,1);
        }
        else if(choice==7)
        {
            proposed_algo(arrival,burst,priority,1);
        }
        else if(choice==8)
        {
            compare_all(arrival,burst,priority,tq);
        }


        cout<<"Press any key for the home page "<<endl;
        char ch;cin>>ch;
    }
}

/*

3
3
5
1
6
2
1
12
3
1


//sp

3
3
5
1
5
20
1
6
2
1
9



*/