College Students go out for a party. To increase social contact, they would love to sit at tables so that no two students from the same programme are at the same table. Show how to find such a seating arrangement or prove that no such seating plan is possible.
The input is the p programmes, for each i the number ai indicates the students from programme i, and the seating capacities of the q tables with table j seating bj people. Give the time complexity of your algorithm with a brief justification.
To grasp this solution easily, try to mentally picture the situation when going through the explanations.
You may like to refer to http://en.wikipedia.org/wiki/Sorting_algorithm for a comparison of sorting algorithms.
Input: Array Students[1..p], Tables[1..q]
// Students[i] gives number of students in program i.
// Tables[i] gives available seating capacity of table i. This array gets modified in this solution.
// p indicates number of programs.
// q indicates number of tables.
// Considering that a worst case NlogN sorting algorithm is chosen wherever sorting is required.
Solution is presented in pseudo-code form along with plain description. Count of comparisons or complexity is marked for various steps in the given implementation. Solution analyzes the given implementation for worst case complexity (in terms of number of comparisons) in achieving a successful seating arrangement.