C++ code for interval scheduling

posted in: C++ | 0

Input: A set of lectures, with start and end times

Goal: Find the minimum number of classrooms, needed to schedule all the lectures such two lectures do not occur at the same time in the same room.

Go through the second section of this short lecture PDF,

   before you try to understand this code….
You also need to have basics of vectors in c++, which you can find here 

Here’s how the code goes…..

# include <stdio.h>
 # include <iostream>
 # include <vector>
 using namespace std;
 //void sort_start_time()
 int main()
 {
vector<int>start_time,end_time;
 int n,i,j,count=0,temp;
 printf("enter the number of lectures to be scheduled");
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
 cout<<"enter the start time of "<<i+1<<" job";
 scanf("%d",&temp);
 start_time.push_back(temp);
 cout<<"enter the end time of "<<i+1<<" job";
 scanf("%d",&temp);
 end_time.push_back(temp);
 }


for(int x=0; x<n; x++)
{
for(int y=0; y<n-1; y++)
{
 if(start_time[y]>start_time[y+1])
 {    
   int temp = start_time[y+1];
 start_time[y+1] = start_time[y];
 start_time[y] = temp;
 temp = end_time[y+1];
 end_time[y+1] = end_time[y];
 end_time[y] = temp;
 }
}
}
int temp_for_end_time;
temp_for_end_time=end_time[0];
 for(i=1;i<n;i++)
 {
 if(start_time[i]<temp_for_end_time)
 {
 count++;
 temp_for_end_time=end_time[i];
 }
}
 cout<<endl<<"number of rooms required"<<count+1;
 return 0;
 }
If you want to have a look at the interval scheduling problem, you can find that here 

Leave a Reply