Uncategorized

Hackerrank Meeting Schedules Solution

Leave a comment

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 &lt; i2.start); 
}  
void mergeIntervals(Interval arr[] , int n ,int range)
{
    if(n &lt;= 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 &lt; 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 &lt; 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 &lt; 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&lt;std::string> ss ;
while (!s.empty()) 
{ 
    Interval t = s.top(); 
    //cout &lt;&lt; "[" &lt;&lt; t.start &lt;&lt; "," &lt;&lt; t.end &lt;&lt; "] " &lt;&lt; cmp &lt;&lt;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, &amp;intpart) *100) )+ (((int)(t.end))*60);
            dur = (24 * 60  - min ) ;
            std::string val1 = (int)t. end &lt; 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, &amp;intpart)*100)&lt; 10 ?( "0" +  std::to_string((int)round(modf (t.end, &amp;intpart) *100))) : std::to_string((int)round((modf (t.end, &amp;intpart)) *100));
            //cout &lt;&lt; t.end &lt;&lt;" " &lt;&lt; val1 &lt;&lt; " " &lt;&lt; val &lt;&lt; endl;
            if(dur >= cmp &amp;&amp; t.end !=0){
                //cout &lt;&lt;  val1 &lt;&lt; " " &lt;&lt; val &lt;&lt; " "&lt;&lt; "00" &lt;&lt; " " &lt;&lt;"00" &lt;&lt; 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, &amp;intpart) )*100) + (int)(t.start)*60;
                dur = min - 0;
                //cout &lt;&lt; "else " &lt;&lt; dur &lt;&lt; endl;

                val1 = (int)t.start &lt; 10? "0" +  std::to_string((int)t.start) :std::to_string( (int)t.start);
                val = round(modf (t.start , &amp;intpart)*100)&lt; 10? "0" +  std::to_string((int)round(((modf (t.start , &amp;intpart)) )*100)) : std::to_string((int)round(((modf (t.start , &amp;intpart)) )*100));

                if(dur >= cmp)
                {
                    //cout &lt;&lt;  "00"  &lt;&lt; " " &lt;&lt; "00" &lt;&lt; " "  &lt;&lt; val1 &lt;&lt; " " &lt;&lt; val &lt;&lt; endl ;
                    ss.push(std::string("00")  + " " + "00" + " "  + val1 + " " + val);
                }
                prev=t;

            }
        }
    else if (s.empty()){

        int min= (int)round((modf (t.end, &amp;intpart) )*100) + (int)(t.end)*60;
        int max= (int)round((modf (prev.start, &amp;intpart) )*100) + (int)(prev.start)*60;
        dur = max - min;

        std::string val2 = (int)t. end &lt; 10? "0" +  std::to_string((int)t. end) : std::to_string((int)t. end);
        std::string val3 = (int)prev.start &lt; 10? "0" +  std::to_string((int)prev.start) : std::to_string((int)prev.start);

        std::string val = (modf (t.end, &amp;intpart))==0 ? "00" : std::to_string((int)round(((modf (t.end, &amp;intpart)) )*100));
        std::string val1= (prev.start - int(prev.start)) ==0 ? "00":std::to_string((int)(round((prev.start - int(prev.start))*100)));

        //cout &lt;&lt; "else " &lt;&lt; dur &lt;&lt; endl;

        if(dur >= cmp){
            //cout &lt;&lt;  val2 &lt;&lt; " " &lt;&lt; val  &lt;&lt; " " &lt;&lt;   val3 &lt;&lt;  " " &lt;&lt; val1 &lt;&lt;endl ;
            ss.push(val2 + " " + val  + " " +   val3 +  " " + val1);
        }
        prev=t;

        //dur = t.start - 0;
       // cout &lt;&lt; "else " &lt;&lt; dur &lt;&lt; endl;
        min= (int)round((modf (t.start, &amp;intpart) )*100) + (int)(t.start)*60;
        dur = min -0;

        val3 = (int)t.start &lt; 10? "0" +  std::to_string((int)t.start) :std::to_string( (int)t.start);
        val = (modf (t.start , &amp;intpart))==0 ? "00" : std::to_string((int)round((modf (t.start , &amp;intpart) )*100));

        if(dur >= cmp)
        {
            //cout &lt;&lt;  "00"  &lt;&lt; " " &lt;&lt; "00" &lt;&lt; " "  &lt;&lt; val3 &lt;&lt; " " &lt;&lt; val &lt;&lt; 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, &amp;intpart) )*100) + (int)(t.end)*60;

        int max= (int)round((modf (prev.start, &amp;intpart) )*100) + (int)(prev.start)*60;

        dur = max - min;

        std::string val = ((modf (t.end , &amp;intpart))*100) &lt; 10  ? "0" +std::to_string((int)round((modf (t.end , &amp;intpart))*100)) : std::to_string((int)round(((modf (t.end , &amp;intpart)) )*100));
        std::string val1= ((modf (prev.start , &amp;intpart))*100) &lt; 10? "0" +std::to_string((int)round((modf (prev.start , &amp;intpart))*100)):std::to_string(((int)round((modf (prev.start , &amp;intpart))*100)));
        std::string val2 = (int)t. end &lt; 10? "0" +  std::to_string((int)t. end) : std::to_string((int)t. end);
        std::string val3 = (int)prev.start &lt; 10? "0" +  std::to_string((int)prev.start) : std::to_string((int)prev.start);

        //cout &lt;&lt; "else " &lt;&lt; dur &lt;&lt; " " &lt;&lt; cmp &lt;&lt; endl;

        if(dur >= cmp)
        {
            //cout &lt;&lt;  val2  &lt;&lt; " " &lt;&lt; val  &lt;&lt; " " &lt;&lt;   val3 &lt;&lt;  " " &lt;&lt; val1 &lt;&lt;endl ;
            ss.push(val2  + " " + val  + " " +   val3 +  " " + val1 );
        }
        prev=t;
    } 
} 

while (!ss.empty()) 
{ 
    cout &lt;&lt; ss.top() &lt;&lt; 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 &lt; 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:

C++ C C# Health concepts Leetcode Programming Data Streucture