# Question: Suppose that we have a set of activities to schedule

Suppose that we have a set of activities to schedule among a large number of lecture halls. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy algorithm to determine which activity should use which lecture hall. (This is also known as the interval-graph coloring problem. We can create an interval graph whose vertices are the given activities and whose edges connect incompatible activities. The smallest number of colors required to color every vertex so that no two adjacent vertices are given the same color corresponds to finding the fewest lecture halls needed to schedule all of the given activities.)

**View Solution:**## Answer to relevant Questions

Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from those ...Show how to solve the fractional knapsack problem in O (n) time. Assume that you have a solution to Problem 9-2.The incidence matrix of a directed graph G = (V, E) is a |V| × |E| matrix B = (bij) such thatDescribe what the entries of the matrix product B BT represent, where BT is the transpose of B.State the type rules for the assignment (“: =”) and equality comparison (“=”) operators. We pointed out that it is strictly incorrect to say that (e.g.) the quantity for a certain shipment is 100 (“a quantity is a value of type QTY, not a value of type INTEGER”). As a consequence, inasmuch as it pretends ...Post your question