CODEWITHSUNDEEP
calgorithmdata-structurestime-complexity
user2684719
user2684719

Reputation:

scheduling greedy choice p‌r‌o‌b‌l‌e‌m

I have an interesting problem to solve with greedy choice.

Given N courses, along with their course strength,

Given M examination halls, along with their capacity;

Assign the courses to examination halls. The upper bound time complexity must be O(MN log M), and space complexity of O(1).

I tried to solve this problem in the similar way of Task scheduling problem using greedy choice. But Task scheduling problem using greedy choice has n log n as run time complexity but I like to solve the problem using time complexity O(MN log M) and space complexity of O(1).

Please suggest a way and data-structure to solve this problem.

Upvotes: 0

Views: 374

Answers (1)

Taylor Brandstetter
Taylor Brandstetter

Reputation: 3623

Assuming N>M, and assuming only one class can be assigned to each hall, and assuming all classes take place at the same time, and assuming your goal is to minimize the number of empty seats, you can start by recognizing the following property:

If "A" is the examination hall with the largest size, and "B" is the largest class that will fit in it, then an optimal solution exists where B is assigned to A.

Why? Suppose we have an optimal solution where B was not assigned to A. If B was assigned to a different classroom "X", and a class "Y" was assigned to hall "A", then we can swap the classes and still have an optimal solution, because Y <= B <= X <= A. If B was not assigned to any classroom, then we can swap it with the class in the largest classroom, and the solution would be improved; therefore it would have not been an optimal solution in the first place (unless the sizes are equal).

Now that we know this, we can just apply it recursively. After placing the largest possible class in the largest examination hall, we end up with a new set of available classes and examination halls, and we can repeat the process.

So one possible algorithm looks like this:

  1. Sort examination halls in decreasing order by number of students: O(M log M)
  2. For each examination hall: O(M)
    • Select largest possible course that will fit in it: O(N)
    • Remove that course from the list

So in this end this is O(M log M + NM), which is a smaller class than O(NM log M).

Upvotes: 2

Related Questions