StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGreedy Algorithm implementation
text
Body
copied!<p>So I have some questions concerning the solution to the problem of scheduling n activities that may overlap using the least amount of classrooms possible. The solution is below:</p> <blockquote> <p>Find the smallest number of classrooms to schedule a set of activities S in. To do this efefficiently move through the activities according to starting and finishing times. Maintain two lists of classrooms: Rooms that are busy at time t and rooms that are free at time t. When t is the starting time for some activity schedule this activity to a free room and move the room to the busy list. Similarly, move the room to the free list when the activity stops. Initially start with zero rooms. If there are no rooms in the free list create a new room.</p> <p>The algorithm can be implemented by sorting the activities. At each start or finish time we can schedule the activities and move the rooms between the lists in constant time. The total time is thus dominated by sorting and is therefore O(n lg n).</p> </blockquote> <p>My questions are </p> <p>1) First, how do you move through the activities by both starting and finishing time at the same time? </p> <p>2) I don't quite understand how it's possible to move the rooms between lists in constant time. If you want to move rooms from the busy list to the free list, don't you have to iterate over all the rooms in the busy list and see which ones have end times that have already passed? </p> <p>3) Are there any 'state' variables that we need to keep track of while doing this to make it work?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload