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)





3 comments:

  1. 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
  2. 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