Algorithms - Lab 4, Problem 1

Introduction

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

a) As few classrooms as possible

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 re