Amazon Interview Question
SDE1sCountry: United States
/// little bit edited and more explained soln of above algo
time complexity : O(nlogn)
typedef struct node
{
int start;
int finish;
}node;
algorithm :
{
1. Use the Priority_Queue <node> data structure
by setting the priority of increasing finish time...
// means the one having less end_time will have greater priority;
2. Then pop first node from priority_queue;
and set last_finish=node.finish;
Then pop nodes from priority_queue until Priority_queue is empty...
if(node.start>last_finish)
{ last_finish=node.finish;
and Doctor is NOT_BUSY in current node appointment
// so appointment is possible
}
else
{
Doctor is BUSY in current node appointment;
// so appointment is not possible in this
}
}// end
----question based on activity selection
Why not maintain a schedule as a binary tree, where key is the starting point and data is the finish time:
for every new appointment
1. search for the node at which this appointment (node) can be inserted, by start times ... O(log n)
2. get the successor of the pre node ... O(log n)
3. check for conflicts: pre.finish < new.start && new.finish < successor(pre).start ... O(1)
return true if no conflicts, and otherwise
input needed :
1. what is the length of the appointment to be scheduled?
2. What is the last time until which an appointment can be scheduled?
once we have these details, follow these steps:
1. arrange already scheduled appointments in increasing order of start time. O(nlogn)
2. traverse through the list and compute difference between end time and start of successive intervals.
3. an appointment can be scheduled if oneo f the following is satisifed:
a) if the gap between any two successive appointments is greater than or equal to the length of the required appointment
b) if there is enough time left in the day after last appointment to accomodate the new appointment
time complexity : O(nlogn)
- v krishna January 10, 2014typedef struct node
{
int start;
int finish;
}node;
solution :
{
1. Use the Priority_Queue <node> data structure
by setting the priority of increasing finish time...
// means the one having less end_time will have greater priority;
2. Then pop first node from priority_queue;
and set last_finish=node.finish;
Then pop nodes from priority_queue until Priority_queue is empty...
if(node.start>last_finish)
return NOT_BUSY;
else BUSY in that appointment;
}// end
----question based on activity selection