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:
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?
