0
$\begingroup$

You can refer the problem on later part of section 4.1 in "Algorithm Design Book by Jon Kleinberg and Éva Tardos"

Problem: We have "n" lectures and we our job is to assign all of the lectures using least amount of classrooms

Let d be the list of resources required, initially we would have resources equal to "n" cause at worst we would require "n" classrooms if "n" lectures overlap with each other

Let's walk through an example:

assume the lectures are as follows and our job is to use minimum number of classrooms with these lectures:

enter image description here

initially d = { 1,2,3,4,5,6,7,8,9,10 }

Pseudocode:

Sort the intervals by their start times, breaking ties arbitrarily

Let I1, I2,..., In denote the intervals in this order

For j = 1, 2, 3, . . . , n
  For each interval Ii that precedes Ij in sorted order and overlaps it
    Exclude the label of Ii from consideration for Ij
  Endfor
  If there is any label from {1, 2, . . . , d} that has not been excluded then
    Assign a nonexcluded label to Ij
  Else 
    Leave Ij unlabeled
  Endif
Endfor

In step 1, we would sort the intervals, which we have already done in the form of ascending "alphabets"

In step 2, we would go through each interval and at for each interval we will compare it with other intervals and accordingly assign labels

j = 1, then interval selected would be "a". Then we will compare "a" with each of the other intervals and not with itself. Since we don't compare it with itself, we won't remove 1 from d and after comparing "a" with each of the other interval. We would still have 1 as the smallest label from d. So we would assign 1 to interval a

j = 2, then interval selected would be "b". Then we will compare "b" with each of the other intervals and not with itself. We would first compare "b" with "a" and since a does precede "b" in terms of start time ( start time of a is less than or equal to b ) and "a" does overlap with "b", we would remove 1 from the d. Then we won't be comparing 2 and since by the end of this interation 2 would be the smallest label, we would assign 2 to the interval "b"

We can trivially see that "c" will have 3 as label, we can prove using the above logic

Let's look at a more interesting case, j = 4, then interval "d" would be selected, we would compare "d" with "a" and since "a" precedes "d" but does not overlap with "a", we can safely assign 1 to it, so we don't remove 1 from d, we then compare "b" with "d" and since "b" overlaps with "d" we would remove 2 from d, and after comparing c we find out we can also assign 3 to "d". But we choose to assign the smallest label, so we would assign 1 to d

And we would process the rest of the intervals the same. And we won't tamper with the inital d, but for every iteration j, we would make a new copy of d and make changes to it

Is my understanding correct?

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    May 11 at 7:16
  • $\begingroup$ We have resources on how to check whether a greedy algorithm is correct or not, here: cs.stackexchange.com/q/59964/755 $\endgroup$
    – D.W.
    May 11 at 7:16

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.