19.3. Interval Scheduling Problem

Try these first

1. 1.

   What is the main goal of the Interval Scheduling Problem?

   Hint

   Think about scheduling without conflicts.

2. 2.

   Define a greedy algorithm.

   Hint

   Remember that it does not backtrack once a decision is made.

3. 3.

   What does the Interval Scheduling Problem aim to maximize?

   • The number of scheduled teachers
   • Total class hours
   • Instructor satisfaction

   Hint

   Focus on the core objective of scheduling.

4. 4.

   True or False: The earliest start time is always the best choice in a greedy strategy for scheduling.

   • True
   • False

   Hint

   Consider examples where conflicting timings exist.

5. 5.

   Given the intervals [1, 3], [2, 5], [4, 6], [7, 9], solve for the maximum number you can schedule without overlaps.

   Hint

   Map out overlapping intervals carefully.

6. 6.

   Prove that the greedy algorithm's choice of the earliest finish time will always produce a solution as good as, or better than, any other possible selection.

   Hint

   Draw on the inductive proof structure to illustrate your claim.