Greedy bug hunt in Python

Questions 1 to 5 of 8

1. 1. This function should return the largest number of meetings that do not clash. ``python def greedy(meetings): ordered = sorted(meetings, key=lambda m: m.start) count = 0 last_end = float('-inf') for m in ordered: if m.start >= last_end: count += 1 last_end = m.end return count `` For the meetings [1, 10], [2, 3] and [4, 5] it returns 1, but the answer is 2. What is the bug?

   The test should be m.start > last_end, so touching meetings are not allowedlast_end should start at 0 instead of float('-inf')The sort key is the start time, so the long meeting [1, 10] is taken first and blocks the two short onesThe count is returned before the loop has gone through all the meetings
2. 2. The correct function sorts meetings by end time. Meetings [3, 9] and [5, 9] both end at 9. Which statement is true?

   Either meeting can come first and the count is 1 either way, because the second one starts before 9 and clashes with the firstTaking [5, 9] first gives a count of 2, because it starts later and leaves more roomThe sort must break this tie by start time, or the count drops to 1The count depends on the order, so the tie must be broken by meeting length
3. 3. What does this Python code print? ``python from dataclasses import dataclass @dataclass(frozen=True) class Meeting: start: int end: int meetings = [Meeting(1, 3), Meeting(3, 4), Meeting(2, 5)] ordered = sorted(meetings, key=lambda m: m.end - m.start) count = 0 last_end = float('-inf') for m in ordered: if m.start >= last_end: count += 1 last_end = m.end print(count) ``

   2013
4. 4. This line is in an otherwise correct greedy function on meetings. What is the bug? ``python ordered = sorted(meetings, key=lambda m: m.end - m.start) ``

   Length does not show what a meeting blocks, so a short meeting in the middle can block two others and cut the countThe loop should compare m.end with last_end instead of m.startlast_end should be set to m.start instead of m.endThe meetings should be sorted by end time in descending order, so the latest one is taken first
5. 5. This loop should take as many meetings as possible. Meetings that touch are allowed. ``python def pick(sorted_meetings): count = 0 last_end = float('-inf') for m in sorted_meetings: if m.start > last_end: count += 1 last_end = m.end return count `` The meetings [1, 3], [3, 5] and [5, 7] all touch, so the answer is 3. This function returns 2. What is the bug?

   last_end should start at float('inf'), so the first meeting is always skippedThe test uses > where it should use >=, so a meeting that starts exactly when the last one ends is droppedThe loop should go from the last meeting to the first, so the latest meeting is taken firstThe sort key should be the length of each meeting, not its end time