cs-136 — The Timetable Collision

Problem

Four study groups — G1, G2, G3, G4 — must book presentation slots. Some pairs share members and cannot present in the same slot:

conflicts: G1–G2   G1–G3   G2–G3   G2–G4   G3–G4

Your deliverables:

1. The model: draw the conflict graph (who is an edge?).
2. A lower-bound argument: why can two slots never suffice? (Point at the specific structure, don't just say "it feels tight".)
3. A three-slot timetable that satisfies every conflict.
4. The trade-off sentence: is "fewest slots" always the right objective? Name one stakeholder for whom it is not.

If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.

Examples

• Input: the five conflict pairs
• Output: minimum 3 slots — e.g. slot 1: G1, G4; slot 2: G2; slot 3: G3 — plus the lower-bound argument

Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.

What to notice

• The conflicts are a graph; slots are colours; the minimum number of slots is the chromatic number — the modelling step does most of the work.
• A lower bound comes from structure: three groups that pairwise conflict need three distinct slots, whatever else happens.
• Greedy first-fit colouring in a fixed order produces a valid answer quickly — but the order can change the count, which matters when the count is the objective.

Discussion starter

After the solution is revealed, the class spends five minutes on this prompt: "A fifth group G5 arrives, conflicting only with G1. Does the minimum stay at 3? Give the timetable or the new lower bound."

Constraints and assumptions

• Difficulty: Advanced (modelling plus an argument, not just an answer).
• Topics: graphs, scheduling, strategy.
• Slots are unbounded in capacity: any number of groups may share a slot as long as no conflicting pair does.
• Classroom-scale inputs unless the problem says otherwise.
• Time-box: about five minutes for a first attempt; partial answers with clear reasoning are worth more than silent struggling.
• Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.

Hints and extension

• First nudge: find three groups where every pair conflicts.
• If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
• After the reveal, attempt the extension below before the next lecture.
• Extension challenge: find a conflict graph on these four groups whose greedy first-fit count depends on the order — and give the two orders.