Else If Clause – Specific Reasons to Use It in Programming

Here is what I would do:

1. Divide the space into a regular lattice of cubes. The the length of the side of each cube should be half the minimum distance between points.
2. For the first point, see which cube it is in. Add a flag to the cube that contains the point to indicate that that cube contains a point of that color.
3. For the next point, see which cube is in. If none of the adjacent cubes are flagged with a point of that color, flag the cube with the color of the point like in (2). Otherwise throw the point away.
4. If you still have unprocessed points, go to 3.

Advantages

The advantages of this approach are:

1. It is fast
2. It is easy to understand and to implement

Limitations

This algorithm has several limitations:

Use of Cubes

The algorithm will throw away too many points because it uses cubes instead of spheres. The question suggests that this is OK.

It it is a problem, however, this limitation can be overcome.

One way is to add the coordinates of the point to the flags. Then, when you test points in step (3) and you find that there is already a point in an adjacent cube, check the distance to that point before you decide whether to throw the point away.

Of course, this will slow things down / add complexity / increase the memory requirements of the algorithm.

Order of Testing Points

The number of points you end up with will depend on the order in which you test the points. To prove this, imagine the situation where you have just 3 red points, and that the cubes they fall into happen to be in a row:

+-----+-----+-----+
|     |   . |     |
|.    |     |     |
|     |     |   . |
+-----+-----+-----+

In this case, you could either throw away the point in the centre cube or the two points in the adjacent cubes.

To improve on the original algorithm, then, you could use the cubes as a basis to count the points of a given color that are tooo close to each other, then throw away the points that have the most points too close. I have not explored this in much depth: I'd need to work through a set of scenarios on paper to figure out the best way to do this.

Memory Use

Another potential problem is that the algorithm could use up quite a lot of memory.

A sensible first step would be to limit the number of cubes created to the minimum by calculate the bounding cuboid for all the points and then only using enough cubes to contain the bounding cuboid.

Another improvement would be to divide the problem into larger cubic regions that contain sub-sets of the full set of points, and processing each of these regions separately. Naturally, special care will need to be taken at the boundaries of thes regions.

I have seen a custom solution for this. Some of the major points:

• There are different approaches to organizing the week, for example the order to actually start 'packing' events can vary. Approaches can include 'Monday first', 'AMs first', '2 day schedule', '6 day schedule', 'A/B schedule'.

• Class size is not an absolute. It's best to have an 'ideal' size plus a minimum and maximum.

• Teachers work different schedules. Some are part time. Some Districts count any hours worked in a given day as having worked a full day. Some count half-days this way and some count quarter days. So the solution tends to be specific to the district.

• It's important to allow and build in some flexibility and 'wiggle-room'. Scheduling resources too 'tightly' leads to issues when the inevitable 'stuff' comes up such as teachers sick, kids sick, weather event days, etc.

• Students enter and leave the district through the year. For some districts that can easily be 20% of their student body. Scheduling algorithms needs to allow for this factor also.

• Special Education has a whole set of requirements including IEP, instruction alone, etc. Also the instructor travel between schools and so distance and travel time has to be incorporated for these services.

• There are different roles to be considered including Teachers, Teacher Assistants, Aides, Translators etc.

• People eat lunch :)

• Teachers need time for Lesson Preparation, Meetings, and Discussions with Parents.

• It is good to distinguish direct Service (actually seeing students) activities as compared to indirect activities.

At the higest level, given your requirements, I would imagine an algorithm for you would be:

For each Course
    For each available Teacher
        For each available Classroom
           Select the first Classroom available and book the resource.
           Update the course and teachers availability.
        end Classrooms
    end Teachers
end Courses