We are given a list of intervals [I1, . . . , In] that denote reserved times for

Question

We are given a list of intervals [I1, . . . , In] that denote reserved times for a room. The times start at t = 0 and end at t = M for a fixed number M. Each interval Ii is of the form (`i , ui) where 0 `i < ui M. 1 Given the list of intervals provide all the time intervals for which the room is free. Your algorithm must run in time (n log(n)) or less. Write down the high level steps of your algorithm and provide pseudocode.

Example: Inputs M = 100, n = 6 and intervals are [I1 : (0, 10), I2 : (8, 9), I3 : (9, 15), I4 : (17, 25), I5 : (25, 35), I6 : (75, 100)

Your output free times should be J1 : (15, 17), J2 : (35, 75)

Hint: Sort the intervals by the finish times.

Explanation / Answer

Assume we storing list of intervals in a tuple data structure.

Pseudocode:
-------------

//sorting intervals by finish times ..
m=100
n=6
for(i=0;i<6;i++){
for(j=0;j<5-i;j++){
if(intervals[j].endingTime > intervals[j+1].endingTime){
temp = intervals[j];
intervals[j] = intervals[j+1];
intervals[j+1] = temp;
}
}
}

//after getting the results
temp = 0
FreeIntervals = {};

for(i=0i<6;i++){
//checking for initital slot
if( i== 0 && intervals[i].startTime >0){
FreeIntervals[temp].startTime = 0;
FreeIntervals[temp].endingTime = intervals[i].startTime;
temp++;
}
//checking for empty slots in between intervals..
else if((intervals[i].endingTime - intervals[i+1].startTime)>0){
FreeIntervals[temp].startTime = intervals[i].endingTime;
FreeIntervals[temp].endingTime = intervals[i+1].startTime;
temp++;
}
}
//finally checking for ending time that is .. M = 1000
if(FreeIntervals[temp].endingTime <1000){ //if last slot is free, then store that time too..
FreeIntervals[temp+1].startTime = intervals[temp].endingTime;
FreeIntervals[temp+1].endingTime = M;
temp++;
}

So finally FreeIntervals contains ... required free time intervals

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.