Just Programming...: Interviewstreet Meeting Schedules - Amazon India Coding Challenge : Solution C++

Saturday, 30 June 2012

Interviewstreet Meeting Schedules - Amazon India Coding Challenge : Solution C++

Interviewstreet Amazon India Coding Challenge

Meeting Schedules Problem

Problem

Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes.

Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes
An event time slot is of form [Start Time, End Time ) . Which means it inclusive at start time but doesn’t include the end time.

Sample Input: Sample Output:

5 120 00 00 09 00

16 00 17 00 17 00 20 45

10 30 15 30

20 45 22 15

10 00 13 25

09 00 11 00

Algorithm

1) Create a bit array busy[ ] of size equal to total no of minutes per day which is 24*60=1440.
             busy[i] = 1 mean minute is busy because of some meeting going on.
             busy[i] = 0 mean minute is free and another meeting can be organized.
             i represent that minute from the day, ex: For 10:30, i would be 10*60+30 = 630
2) For each input interval, fill busy[i] array on that interval.
3) After each input interval is processed, start scanning busy[ ] array from 0 to 1440 for k continuous
    free minutes.And whenever you find the interval print the interval. There may be more than 1 such
    interval.

Have a better approach in mind, please share it for our readers in comments section.

Solution

//All test cases passed

#include<iostream>
using namespace std;

void print(int i) {
if(i==0 || i==1440) cout << "00 00";
else {
     int j = i/60;
     int k = i%60;
     if(j<10) cout << "0" << j << " ";
     else cout << j << " ";
     if(k<10) cout << "0" << k ;
     else cout << k ;
}
}

int main()
{

int m,k;
cin>>m>>k;
int busy[1440];
int a1,a2,b1,b2;
int i;
for(i=0;i<1440;i++)
    busy[i]=0;

while(m--) {

    cin>>a1>>a2>>b1>>b2;
    int start = a1*60+a2;
    int end = b1*60+b2;
    for(i=start;i<end;i++)
        busy[i]=1;

}
int j;
i=0;
while(i<1440) {
    j=i;
    if(busy[j] == 1) {
        i++;
        continue;
    }
    while(j < 1440 && busy[++j]!=1);
    if((j-i)>=k) {
       //cout << i << " " << j << endl;
       print(i);
       cout << " ";
       print(j);
       cout << endl;
    }
    i=j;
}

//cin >> i;

}

Time Complexity

Busy array is scanned twice, so O(n)

5 comments:

.....ಆಗ ಸಂಜೇ ಆಗಿತ್ತ......9 March 2013 at 00:19
This comment has been removed by the author.
ReplyDelete
Replies
Unknown11 October 2013 at 10:04
I dont think we need an array of size 24*60 . Here's my algorithm :

struct time {
int start_time;
int end_time;
};

1) keep an array of struct time of size M;
2) sort the array on the basis of start_time;
3) Now traverse through the array :
when we are at index 'i' : print the value : start_time[i+1] - end_time[i]
ReplyDelete
Replies
Unknown27 October 2013 at 22:08
Hi,

I tired this problem using C++

My Alogirthm is:

1) Sort the array by start time
2) calculating difference between Start time and End time of Alternate schedules.

##Note## this program passed First 7 test cases.

Can you please assist me where i did mistake..Which one i forgot to check.?

Here's my code.

#include
#include
#include
#include

using namespace std;

class meeting_Shld
{
vector slot;
int M,K,val,T,Time_sec,Start_HH=0,Start_MM=0,End_HH=24,End_MM=0;
void getData()
{
cin>>M>>K;
T=M*4;
// cout<>val;
slot.push_back(val);
}

}

void swapp(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
//cout<< """ """<<*b<<" "<<*a<<" "<slot[j])
{
swapp(&slot[i],&slot[j]);
swapp(&slot[i+1],&slot[j+1]);
swapp(&slot[i+2],&slot[j+2]);
swapp(&slot[i+3],&slot[j+3]);

}
else if(slot[i]==slot[j])
{
if(slot[i+1]>slot[j+1])
{
swapp(&slot[i],&slot[j]);
swapp(&slot[i+1],&slot[j+1]);
swapp(&slot[i+2],&slot[j+2]);
swapp(&slot[i+3],&slot[j+3]);

}
}

}

}
void display()
{
for(int i=0,j=1;i=0)
{
Time_sec=Time_sec+(slot[1]-Start_MM);
//cout<=K)
cout<=0)
{
Time_sec=Time_sec+(slot[i+3]-slot[i+1]);
if(Time_sec>=K)
cout<=0)
{

Time_sec=Time_sec+(End_MM-slot[T-1]);
//cout<=K)
cout<<setw(2)<<setfill('0')<<slot[T-2]<<" "<<setw(2)<<setfill('0')<<slot[T-1]<<" "<<setw(2)<<setfill('0')<<End_HH-24<<" "<<setw(2)<<setfill('0')<<End_MM<<endl;

}

}

//-----------------------------End of day --------------------------------------------------------------------------------------------------------------

}

public:

void get_start()
{
getData();
sortData();
//display();
//cout<<endl;
getMeeting();

}

};

int main()
{
meeting_Shld ms;
ms.get_start();
return 0;
}

ReplyDelete
Replies

Add comment

Just Programming...

Labels