Greedy Activity-Selector algorithm: n activities in smallest amout of lecture halls pseudo code

Question

I have spent hours trying to understand the answer to this problem. I just don't get it. Can somebody please give me some pseudo code (preferably pseudo code similar to Java) of the algorithm that would solve this problem based on the answer? That will help me understand what the answer is trying to say.

Question and answer:

Rather than typing it all out, it's styled better in this PDF. The question is the first one on the pdf, Exercise 16.1-4

http://mitpress.mit.edu/algorithms/solutions/chap16-solutions.pdf

(To clarify, his is not homework, I am doing the bookwork and want to understand this problem. The link is the solution to the problem, but I don't understand it. I don't understand what it means when it says "To do this, move through a set of events consisting of activities starting and activities finishing, in order of event time..." and the rest of the explanation. This is why, if someone understands it, I would like if they could show me the pseudo code of what this is explaining. I could read and understand it that way. Like what the parameters of the function would be, and what is going on inside the function, how the activities are iterated through, how they move between the two lists of busy and free arrays of lecture halls, etc.) Thank you

Answer 1

Okay, I'm not going to answer this with proper code, and at most I'll have pseudocode as I try to define what I understand of the problem. I will also make the assumption that you'll use integer times, as opposed to floating point times, though I'm sure it wouldn't make a massive difference at the end of the day.

The greedy solution here is to simply assign to a free lecture hall, and always use lecture halls that have been used previously. That is, I'm pretty sure, what the solution is asking for you to do.

So, firstly, I would create some kind of struct or class that holds all the "events", where we define an "event" to be either the starting or finishing time of an activity. This struct/class would also hold a reference to what activity it was the start/finishing time of.

Maybe kinda like (C++ syntax because it's easier and I'm lazy):

struct evt
{
    int activityID;
    int time;
    bool isStart;
};

The next step would be to construct an instance of this struct or class for each activity's start/finish time, and then place it into some sort of list data structure (if this was C++, I'd use a vector, and I guess ArrayList for Java) and then sort the events based on their time. So, for Java, you'd need some kind of comparison function that determines an ordering for these events based on their time. Also, within your comparator, an event that is a starting event would go later than an event that is a finishing event (remember, the intervals are half-open). I'll call the ArrayList "eventList".

Next, you have two lists of what I'd assume are n halls (you would need at most n halls to run all the activities). One list has all the halls. This is the list of halls that are not in use. The other list is empty. This will be the list of halls that are in use. These would be lists that can remove from their front (the Java ArrayList can do this, I think).

You'd have some way of identifying a hall, and maybe some kind of reference array so that each activity could be assigned to a hall. This part is a little unclear, and I'd rather leave the implementation details to you, but if n wasn't too large I would probably have (again with the C++) a vector<int> of size n, and the i-th element in that vector would be the hall identifier, or -1 if it hadn't been assigned yet. And if I was trying this in Java, this would be an int[n] array.

Then I would iterate through eventList, and at each event, I would check to see if it was a finishing time or a starting time. If it's a starting time, I would take the front element of the "free halls" list and put it into the "in-use" halls. If it was a finishing time, I'd take the hall that had just finished, remove it from the "in-use" list and put it back to the front of the "free halls" list. Remember, you'd also need to update that reference array I talked about earlier.

Finally, with a bit of tinkering, you could find how many halls had been used. A linear pass through the array or a counter that was running as you were using halls would have been sufficient. One way I think works is to record the maximum size of the list that holds how many halls are in use at one time, though this may be incorrect (haven't tested it thoroughly).

I'm just doing this out of the top of my head, so this solution is probably a bit confusing at the moment. Sorry about that. I'll try and summarise it here:

1. Declare a class that summarises the start/finishing times as events
2. Sort all the start and finishing times into an array, with earlier times going earlier in the list, and finishing times appearing before starting times
3. Make a list of the halls, and another (empty list) which will be all the halls being used
4. Process each event, moving a hall to the in-use list if it's a starting time, and to the free list if it's a finishing time

Since this is quite a long post, and I haven't provided much code (I tried dropping hints but I don't know whether it was helpful) please let me know if you have more questions and I will attempt to help as best I can.

The "activity selection" problem, as seen here can be solved in a greedy fashion by always choosing the activities that finish earliest. I think this is a little different, but I've just included it because it might be interesting.

Answer 2

Here is my Java Implementation of Lecture Hall Greedy Selector Algorithm using Java Collections

https://github.com/pratikmp/LectureHallGreedyAlgorithm