Exercise 2: What Changes Under the Strict (No-Touching) Interpretation — Possible Solution ==================================================================== RE-RUNNING THE GREEDY ALGORITHM WITH THE STRICT RULE ------------------------------ Under the strict interpretation, a room can only be reused if its current occupant's end time is STRICTLY earlier than the new talk's start time (end < start), rather than this chapter's own original rule (end <= start, where touching is allowed). Re-running the identical greedy algorithm on the same six talks with only this one rule changed produces a genuinely different result: 4 rooms needed instead of 3, with assignment {A:0, B:1, F:2, C:3, D:0, E:1}. WHY THE ROOM COUNT INCREASES SPECIFICALLY ------------------------------ The original result relied directly on being able to reuse a room the moment its previous occupant ended, at the exact instant the next one begins - Room 0 reused A's slot (ending at 10) for C (starting at 10), and later reused C's slot (ending at 12) for E (starting at 12). Under the strict rule, neither of these reuses is allowed anymore, because "ending at 10" and "starting at 10" are now considered a genuine conflict. This forces the algorithm to open new rooms specifically at the two points where the schedule previously relied on a touching-endpoint reuse, which is exactly why the room count goes up by one, from 3 to 4. WHY THIS DOESN'T CONTRADICT THIS CHAPTER'S OWN OPTIMALITY CLAIM ------------------------------ This chapter's tip box explained that the minimum number of rooms always equals the maximum number of talks overlapping at any single instant - AND that this equivalence, along with the greedy strategy itself, still holds regardless of which specific overlap rule is being used, as long as it's applied CONSISTENTLY throughout. Recomputing the maximum overlap under the strict rule (where a talk ending and another starting at the same instant now counts as 1 extra unit of temporary overlap) would independently confirm that 4 is genuinely the new minimum under this stricter definition - the greedy algorithm is still producing the correct, optimal answer; only the DEFINITION of what counts as a conflict changed, which naturally changes what the optimal answer actually is. WHY THIS WORKS AS AN ANSWER ------------------------------ The answer actually re-derives the new result under the changed rule rather than guessing, identifies precisely which two room-reuse decisions from the original result are no longer valid, and correctly distinguishes "the definition of the problem changed" from "the algorithm's own correctness broke," consistent with this chapter's own emphasis on resolving ambiguity precisely before trusting any result.