Interval Scheduling Problem

Please help me how to solve it - Given a set of meeting intervals, each with a start and end time. Check whether a meeting room can schedule all the meetings.

Input :
0 30
5 10
15 20

Output :
No

make a vector pair as : vector < pair < int ,int > > vect in c++
then sort this list of two dimension vector on the basis of first element as
sort(vect.begin(),vect.end());
then check if for all i if(vect[i].second<vect[i+1].first) is true then answer is YES else NO

To solve it, Sort the intervals on the basis of starting time of each interval by making vector of pairs,where a pair represents (start_time,end_time) of an interval . Now for each interval , finishing time should be less than the starting time of the next interval. If it is true then YES ,all meetings can be scheduled otherwise NO.
for more clarity see the implementation below,

vector<pair<int,int> > v;
int n, i;
SCAN n ;
for(i= 0;i LESS THAN n ;i++){
     int start_time, end_time;
     SCAN start_time AND end_time  ;
     v.push_back(make_pair(start_time,end_time)) ;
}
sort(v.begin(),v.end()) ;
for(i= 1; i LESS THAN n ;i++){
    if(v[i].first GREATER THAN  v[i-1].second)
        continue ;
    else
        break;
}
if(i!= n) PRINT "NO"
else   PRINT "YES"
1 Like