vendredi 24 août 2018

Programming challenge: How to find out how many customers are at the same time in a restaurant?

I have to what is the largest amount of customers at a time. The only input i'm given is the amount of customers that visit a restaurant and their arrive and departure times. The amount of customers ranges from 1 to 10^5. Here is my code, how can i optimize it to solve the task in under 1 second?

include<bits/stdc++.h>
using namespace std; 
int main()
{
unsigned n,temp0,temp1,longest=0,counter=0;
cin>>n;
    vector<pair<int,int>> vect;

    for (unsigned i=0; i<n; i++){
        cin>>temp0>>temp1;
        if(temp0>longest){longest=temp0;}
        if(temp1>longest){longest=temp1;}
        vect.push_back(make_pair(temp0,temp1));
    } 
    sort(vect.begin(), vect.end());
    unsigned record=0;
    for (unsigned i=0;i<longest;i++){
        counter=0;
        for(unsigned j=0; j<n; j++){
            if(vect[j].first<i && i<vect[j].second){
                counter++;
            }
        }
        if(counter>record){
            record=counter;
        }
    }
    cout<<record;
}

Aucun commentaire:

Enregistrer un commentaire