Hackerrank Meeting Schedules Solution
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.
Input Format:
M K [ M number of busy time slots , K is the duration in minutes ]
Followed by M lines with 4 numbers on each line.
Each line will be of form StartHH StartMM EndHH EndMM [ Example 9Am-11Am time slot will be given as 9 00 11 00 ]
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.
So an event of form 10 00 11 00 => implies that the meeting start at 10:00 and ends at 11:00, so another meeting can start at 11:00.
Sample Input:
5 120
16 00 17 00
10 30 14 30
20 45 22 15
10 00 13 15
09 00 11 00
Sample Output:
00 00 09 00
17 00 20 45
Sample Input:
8 60
08 00 10 15
22 00 23 15
17 00 19 00
07 00 09 45
09 00 13 00
16 00 17 45
12 00 13 30
11 30 12 30
Sample Output:
00 00 07 00
13 30 16 00
19 00 22 00
Constraints :
1 <= M <= 100
Following solution return in C++ pases all test cases.
<p>using namespace std;</p>
<!-- /wp:html -->
<!-- wp:paragraph -->
<p>struct Interval<br>
{<br>
float start , end;<br>
};<br>
bool compareInterval(Interval i1, Interval i2) <br>
{ <br>
return (i1.start < i2.start);
}
void mergeIntervals(Interval arr[] , int n ,int range)
{
if(n <= 0)
return;
stack s; </p>
<!-- /wp:paragraph -->
<!-- wp:html -->
// sort the intervals in increasing order of start time
sort(arr, arr+n, compareInterval);
// push the first interval to stack
s.push(arr[0]);
// Start from the next interval and merge if necessary
for (int i = 1 ; i < n; i++)
{
// get interval from stack top
Interval top = s.top();
// if current interval is not overlapping with stack top,
// push it to the stack
if (top.end < arr[i].start)
s.push(arr[i]);
// Otherwise update the ending time of top if ending of current
// interval is more
else if (top.end < arr[i].end)
{
top.end = arr[i].end;
s.pop();
s.push(top);
}
}
float cmp = range;/// 60 + (float)(range %60)/100;
bool first=true;
double intpart;
Interval prev;
stack<std::string> ss ;
while (!s.empty())
{
Interval t = s.top();
//cout << "[" << t.start << "," << t.end << "] " << cmp <<endl;
float dur;
s.pop();
if(first){
dur = (24 - t.end ) ;
//use modf to get accurate floating point results
// modf returns the fraction part but on multiplying and typecasting to int , it may give unexpected results so round function is used before typecasting to int
int min= (int)(round(modf (t.end, &intpart) *100) )+ (((int)(t.end))*60);
dur = (24 * 60 - min ) ;
std::string val1 = (int)t. end < 10 ?( "0" + std::to_string((int)t. end)) : std::to_string((int)t. end);
// if single digit append a zero
std::string val = round(modf (t.end, &intpart)*100)< 10 ?( "0" + std::to_string((int)round(modf (t.end, &intpart) *100))) : std::to_string((int)round((modf (t.end, &intpart)) *100));
//cout << t.end <<" " << val1 << " " << val << endl;
if(dur >= cmp && t.end !=0){
//cout << val1 << " " << val << " "<< "00" << " " <<"00" << endl ;
ss.push(val1 + " " + val + " " + "00" + " " +"00");
}
prev=t;
first=false;
// case when there is only one duration , so range may include interval on both sides of it
if(s.empty())
{
min= (int)round((modf (t.start, &intpart) )*100) + (int)(t.start)*60;
dur = min - 0;
//cout << "else " << dur << endl;
val1 = (int)t.start < 10? "0" + std::to_string((int)t.start) :std::to_string( (int)t.start);
val = round(modf (t.start , &intpart)*100)< 10? "0" + std::to_string((int)round(((modf (t.start , &intpart)) )*100)) : std::to_string((int)round(((modf (t.start , &intpart)) )*100));
if(dur >= cmp)
{
//cout << "00" << " " << "00" << " " << val1 << " " << val << endl ;
ss.push(std::string("00") + " " + "00" + " " + val1 + " " + val);
}
prev=t;
}
}
else if (s.empty()){
int min= (int)round((modf (t.end, &intpart) )*100) + (int)(t.end)*60;
int max= (int)round((modf (prev.start, &intpart) )*100) + (int)(prev.start)*60;
dur = max - min;
std::string val2 = (int)t. end < 10? "0" + std::to_string((int)t. end) : std::to_string((int)t. end);
std::string val3 = (int)prev.start < 10? "0" + std::to_string((int)prev.start) : std::to_string((int)prev.start);
std::string val = (modf (t.end, &intpart))==0 ? "00" : std::to_string((int)round(((modf (t.end, &intpart)) )*100));
std::string val1= (prev.start - int(prev.start)) ==0 ? "00":std::to_string((int)(round((prev.start - int(prev.start))*100)));
//cout << "else " << dur << endl;
if(dur >= cmp){
//cout << val2 << " " << val << " " << val3 << " " << val1 <<endl ;
ss.push(val2 + " " + val + " " + val3 + " " + val1);
}
prev=t;
//dur = t.start - 0;
// cout << "else " << dur << endl;
min= (int)round((modf (t.start, &intpart) )*100) + (int)(t.start)*60;
dur = min -0;
val3 = (int)t.start < 10? "0" + std::to_string((int)t.start) :std::to_string( (int)t.start);
val = (modf (t.start , &intpart))==0 ? "00" : std::to_string((int)round((modf (t.start , &intpart) )*100));
if(dur >= cmp)
{
//cout << "00" << " " << "00" << " " << val3 << " " << val << endl ;
//putting in another stack to give result in ascending order, a better solution was to use just one queue
ss.push(std::string("00") + " " + "00" + " " + val3 + " " + val);
}
prev=t;
}
else{
//dur = prev.start - t.end;
int min= (int)round((modf (t.end, &intpart) )*100) + (int)(t.end)*60;
int max= (int)round((modf (prev.start, &intpart) )*100) + (int)(prev.start)*60;
dur = max - min;
std::string val = ((modf (t.end , &intpart))*100) < 10 ? "0" +std::to_string((int)round((modf (t.end , &intpart))*100)) : std::to_string((int)round(((modf (t.end , &intpart)) )*100));
std::string val1= ((modf (prev.start , &intpart))*100) < 10? "0" +std::to_string((int)round((modf (prev.start , &intpart))*100)):std::to_string(((int)round((modf (prev.start , &intpart))*100)));
std::string val2 = (int)t. end < 10? "0" + std::to_string((int)t. end) : std::to_string((int)t. end);
std::string val3 = (int)prev.start < 10? "0" + std::to_string((int)prev.start) : std::to_string((int)prev.start);
//cout << "else " << dur << " " << cmp << endl;
if(dur >= cmp)
{
//cout << val2 << " " << val << " " << val3 << " " << val1 <<endl ;
ss.push(val2 + " " + val + " " + val3 + " " + val1 );
}
prev=t;
}
}
while (!ss.empty())
{
cout << ss.top() << endl;
ss.pop();
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int t ;
cin >> t ;
int range ; cin >> range ; Interval arr[t] ; for(int i=0 ; i < t ; i ++) { int a, b ,c , d ; cin >> a ; cin >> b ; cin >> c ; cin >> d ; Interval e ; e.start =a + (float)b/100 ; e.end=c + (float)d/100; arr[i] = e; } mergeIntervals(arr,t,range); return 0;
}
Solution: