Problem
Most non-overlapping classes in one day
Nine classes run in one day. Each has a fixed start time and finish time. No two chosen classes may overlap. Find the most classes that can be attended.
Reasoning · Grade 6-2 Optimal Design
Your answer
Watch out Shortest-first is tempting, but earliest-finishing first fits the most.
How to solve
Strategy Draw a Diagram — Printed as a table, nine pairs of times are hard to compare; drawn as nine bars on one time line running from 6 a.m. to 8 p.m., the clashes jump out and the empty stretches of the day become visible. The second move is to re-sort the list -- not by the order printed and not by start time, but by finishing time -- because the class that finishes earliest is the one that leaves the most of the day still free, and that ordering turns the search into a single sweep left to right instead of a hunt through hundreds of combinations. Building the chain that way is a systematic list, and it produces the example. For the upper bound the trick is to stop looking at classes and look at moments instead: if a handful of clock times can be found so that every class is in session at one of them, then Mia's classes are forced to use up different moments, and counting the moments caps the answer.
1STEP 1
Put every class on one time line
Put all nine on one time line.
A time line turns 'do these clash?' into 'do these bars touch?', a question a young solver can answer by looking instead of by comparing four numbers at once.
3.MD.A.1Draw A Diagram2STEP 2
Re-sort the timetable by finishing time
Re-sort them by finishing time.
Sorting by end time is just ordering nine clock readings, and it captures the whole idea of the problem: getting free early is what leaves room for more classes.
3.MD.A.1Organize Information In More Ways3STEP 3
Build a chain of classes, always taking the earliest finisher available
Chaining earliest finishers gives four classes.
7{:}00→10{:}00, 11{:}00→13{:}00, 14{:}00→17{:}00, 18{:}00→20{:}00
Each pick is a small comparison of two clock times -- 'does this start after I get out?' -- and taking the earliest finisher each time means no other choice could have left more room.
4.OA.A.3Make A Systematic List4STEP 4
Check that the four really do fit
The four do not overlap.
10{:}00 ＜ 11{:}00, 13{:}00 ＜ 14{:}00, 17{:}00 ＜ 18{:}00
Checking a schedule means checking neighbours only: if each class ends before the next begins, the whole day is clash-free.
3.MD.A.1Make A Systematic List5STEP 5
Pick four moments that catch every class
Pick four moments that catch every class.
4 + 2 + 2 + 1 = 9
Instead of asking which classes clash with which -- 36 pairs to check -- ask one much smaller question about four chosen instants, and nine quick 'is it running now?' checks settle it.
3.MD.A.1Change Focus Count The Complement6STEP 6
Count the moments to cap the answer at four
One class per moment caps it at four.
at most 1 class per moment × 4 moments = 4
This is the pigeonhole idea in everyday clothes: four moments can hold at most four non-clashing classes, the same way four chairs can seat at most four children.
4.OA.A.3Change Focus Count The ComplementFour well-chosen moments catch every class, so no more than four classes can be attended.
Why?
Every class is running at one of those four moments, so a fifth attended class would have to share a moment with another.
🧱More items than boxes forces a shared boxn boxes can hold at most n items one apiece, so item number n plus one has nowhere new to go and must share.
Why?
Two classes running at the same moment clash, so a workable timetable can use each moment for at most one class.
🧱One-to-one correspondenceIf each thing here pairs with exactly one thing there, the two groups are the same size.
7STEP 7
Notice the one other way to reach four
So the most attendable is 4 classes.
Finding a second answer that also reaches four is a good check that four is genuinely the ceiling and not an accident of the order the classes were picked.
4.OA.A.3Make A Systematic ListAnswer
4 classes
4 + 2 + 2 + 1 = 9
The answer is a count of classes, so it should be a whole number between 1 and 9, and 4 is. A rough size check agrees: the four chosen classes take 3 + 2 + 3 + 2 = 10 hours out of the 14 hours from 6 a.m. to 8 p.m., which is a full but believable day, while five classes would need at least 2 + 2 + 3 + 3 + 3 = 13 hours of the 14 -- and those five shortest classes include Art Therapy, Kids' Gymnastics and Speech and Language, which all pile into the same morning, so they could never be squeezed in without clashing. The two halves of the answer also agree with each other: the schedule of four is exhibited, and the four moments 9:30 a.m., 11:30 a.m., 3:30 p.m. and 7 p.m. catch all nine classes and cap the count at four.
Takeaway
Always grab the class that finishes earliest -- and to prove nobody can do better, find a few moments that every single class is running through.
- Put every class on one time line
- Re-sort the timetable by finishing time
- Build a chain of classes, always taking the earliest finisher available
- Check that the four really do fit
- Pick four moments that catch every class
- Count the moments to cap the answer at four
- Notice the one other way to reach four