Interview Question
Country: United States
- Sort the two arrays.
- Now iterate over the two arrays doing +1 for every start time and -1 for every end time.
- Track the maximum.
e.g. start time 9:00 10:00 10:50 11:10 11:20
end time 9:30 12:00 11:00 11:30 12:00
sorted 9:00 10:00 10:50 11:10 11:20
9:30 11:00 11:30 12:00 12:00
1 0 1 2 1 2 3 2 1 0
so 3 classrooms are needed.
Sort the intervals in order of increasing finish times.
- Aashish June 25, 2012If the current interval start time is >= previous interval finish time, include it,else leave it.
Do the above steps until no more intervals are left. Meanwhile keep incrementing number of classes.