CODEWITHSUNDEEP
dynamic-programming
athul777
athul777

Reputation: 207

Variation of weighted interval scheduling given fixed number of classrooms

I had a question about solving a weighted interval scheduling problem given a fixed number of classrooms. So, initially, we are given a set of intervals, each with a starting time and finishing time, and each with a weight. So, the aim of the problem is to find a scheduling in two classrooms that maximizes the weight. Is there an efficient way to do this by dynamic programming?

My approach was trivial, since I built an algorithm that simply maximizes the intervals for each classroom. Is there a better way to do this?

Upvotes: 0

Views: 329

Answers (1)

Math10
Math10

Reputation: 1043

My idea is not fully dynamic programming. But I think it will help.

  1. Sort all classes by their starting time.
  2. Now for a class i find next class j which start time is greater or equal then this end time. (Using binary search you can find this because we have an sorted array which is sorted by starting time)
  3. Assume max_so_far is an array and max_so_far[z] contain the max_weight class from z to last
  4. For all i find the max of summation of weight of class[i] and weight max_so_far[j]

Please find the code here Time complexity of this code is O(nLog(n)).

Upvotes: 1

Related Questions