authorea.com/7140

Algorithms - Lab 4, Problem 1

This is a hand-in written by **Group 7** (FIRE) for the Algorithms course (**TIN092**) at Chalmers University of Technology.

Group 7 consists of:

**Mazdak Farrokhzad**901011-0279

twingoow@gmail.com

Program: IT

**Niclas Alexandersson**920203-0111

nicale@student.chalmers.se

Program: IT

The number of rooms required to schedule a number of lectures is equal to the largest number of lectures which occur at the same time. It is trivial to see that this is the lower bound for the answer; if there are \(k\) lectures which occur at the same time, then there must also be at least \(k\) rooms available in order to be able to schedule them all in separate rooms. Intuitively, if we see time as a line with different levels, and each of the levels represent a room, and then go from left to right trying to place legtures as “far down” as possible, the only reason for placing a lecture at level \(m\) would be if it conflicted with lectures on all the \(m-1\) levels below. Therefore, the upper bound will also be the largest number of lectures colliding at the same time.

We therefore write an algorithm that given a set of lectures, returns the largest number of simultaneously colliding lectures. The algorithm goes through all lectures in start time order, and compares them against the set of lectures which the previous lecture collided with, to see if they also collide with these. The algorithm then returns the size of the largest set of colliding lectures encountered.

```
def efficient_lsp(courses):
courses <- sorted(courses, key=lambda c: c.start())
collisions <- priority_queue(sorted: key=lambda c: c.finish())
maxcol <- 0
for i in courses:
while len(collisions) > 0 and !collides(i, collisions.peekFirst()):
collisions.removeFirst()
collisions.add(i)
maxcol <- max(maxcol, len(collisions))
return maxcol
```

[H]

[1] \(collisions.removeFirst()\) \(collisions.add(i)\)

We assume that we have access to a priority queue with operations \(`peekFirst()`

\in \ordo{1}\), \(`removeFirst()`

\in \ordo{\log{n}}\), and \(`add()`

\in \ordo{\log{n}}\). This can be achieved through using a heap.

To calculate the complexity of the above algorithm, we must realise that the body of the inner loop will only execute a total number of times equal to the total number of elements placed in the collisions queue. Since no element is placed in the collisions queue more than once, this means that this number cannot be greater than \(n\), and since the last element is always added after the loop condition is checked the last time, we get that in fact, it cannot be greater than \(n-1\). The loop condition of the inner loop will be evaluated the number of times that the inner loop body is run, plus one more per iteration of the outer loop. This gives us the complexity function:

\[\begin{aligned} T(n) &= c_0 + n\log{n} + (n-1) (c_1 + \log{n}) + n (c_1 + c_2 + \log{n})\\ &= 3n\log{n} + n (2c_1 + c_2) - \log{n} + c_0 - c_1\\ &\in \ordo{n\log{n}}\end{aligned}\]

The earlier algorithm will only give us the number of rooms required, and not the actual schedules for each room. We therefore write an algorithm that is based on the same principle, but instead of checking how many earlier lectures a given lecture collides with, the algorithm simply tries to find a room in which the new lecture can be added without conflicting with earlier lectures, and adds a new room if no such room is found.

```
def efficient_lsp(courses):
courses <- sorted(courses, key=lambda c: c.start())
rooms <- priority_queue(sorted: key=lambda r: r.getLast().finish())
for i in courses:
room <- []
if len(rooms) > 0 and !collides(i, rooms.peekFirst().getLast()):
room <- rooms.removeFirst()
room.addLast(i)
rooms.add(room)
return asList(rooms)
```

[H]

[1] \(room.addLast(i)\) \(rooms.add(room)\)

We assume that we have access to some form of sequential data structure with operations \(`addLast()`

\in \ordo{1}\), and \(`getLast()`

\in \ordo{1}\) and that our priority queue can be converted to a sequential data structure in linear time.

Complexity:

\[\begin{aligned} T(n) &= c_0 + n\log{n} + n (c_1 + \log{n}) + n\\ &= 2n\log{n} + c_1 n + n\\ &\in \ordo{n\log{n}}\end{aligned}\]

We can easily convert the problem into a graph colouring problem, by treating each lecture as a node, and adding edges between all lectures which overlap, and therefore conflict with each other.

```
reduce_lsp(courses):
edges <- []
for i in courses:
for j in courses:
if i /= j && isCollision(i, j)
edges.add( (i, j) )
return edges
```

[H]

[1] \(\textbf{add}(edges, (i,j) )\)

Complexity:

## Share on Social Media