In this edition, I take up a slightly more complex case than the previous one.
We developed (ok … still developing …) a product to host online contests. The challenge about contests is that it is a time-restricted-event. High performance and availability is a must during the entire course of the event. More about these later. Here I wish to explain a requirement and how we used the algorithm to fulfill the requirement.
In a particular online contest, the participants take part on behalf of their schools. The online contest is divided into many sessions. If there are 20 schools taking part in total and if the online competition is held in 4 sessions, then, in an ideal scenario, they are split into 5 schools per session.
Enter some more conditions – Each session can handle a fixed capacity (of users). Cannot accommodate any more without compromising on performance/availability. The number of participants in each school vary. All the students belonging to a school would take part in the same session. This means, students of a school cannot be split across many sessions.
A numerical example would help understand better
Session capacity = 100 users
number of sessions = 2
School representation = schools S1 has 45 students, school S2, 89 and school S3 has 27 students.
To accommodate the above schools, The first session shall have School S2 (89 students) and the next session shall have the schools S1 (45) and S3 (27). I guess this gives a fair idea.
A little thought provides us with the bare bone problem statement.
“Given a set of integers, how can it be split into K partitions such that each partition has max capacity C and the split is optimal”
We did not attempt to write the algorithm ourselves. We googled for some words in the above problem statement and voila! … there we had the plan of the algorithm. I would spare any explanation. Please refer to this http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK2/NODE45.HTM
Note that the previous problem (part 1) was a special case of this problem where there were just two partitions and no max capacity.
The key learning, in this experience, is that, when a problem is well understood and when the problem can be expressed concisely, it is then, only a matter of searching for a solution. Not being a pro at Algorithms is not a handicap. Don’t get me wrong here … I don’t mean to say it is OK not to know Algorithms … knowing algorithms like the back of your hand is really really helpful. In fact, more your grasp in algorithms, better a person you are ! OK … I will re-phrase … Not knowing ALL algorithms is not a handicap.
If any one needs a java implementation of the above algorithm, please leave a comment. Either V or myself would send it to you.