Market stall bookings
A weekend market has one stall available for hire, and traders send in booking requests as a start hour and an end hour on the same day. The stall can only serve one trader at a time, but a new booking may begin at exactly the hour the previous one ends. The market manager wants to accept as many bookings as possible.
Read the requests and print the maximum number of bookings that can be accepted without any two overlapping.
Input
The first line is an integer n. Each of the next n lines is start end, two integers with 0 <= start < end <= 24.
Output
One line: the largest number of non-overlapping bookings.
Example 1
Input
4 8 20 8 10 10 12 12 14
Output
3
Taking the all-day booking 8-20 blocks everything else. Taking 8-10, 10-12 and 12-14 instead gives three bookings that touch but do not overlap.
Example 2
Input
3 9 12 10 13 11 14
Output
1
Every pair of these bookings overlaps, so only one can be accepted.
Constraints
- 1 <= n <= 1000
- 0 <= start < end <= 24
- A booking ending at hour h and another starting at hour h do not overlap
Hints
Hint 1 of 3
Trying every subset is hopeless at 1000 bookings. Think about which booking is always safe to accept first.
Hint 2 of 3
The booking that ends earliest leaves the most room for everything after it. Sort by end time.
Hint 3 of 3
Walk the sorted list keeping the end hour of the last accepted booking; accept a booking when its start is at or after that hour, and update the end.
Solution
Show a reference solution and explanation
int count = int.Parse(Console.ReadLine()!);
var bookings = new List<(int Start, int End)>();
for (int i = 0; i < count; i++)
{
string[] p = Console.ReadLine()!.Split(' ');
bookings.Add((int.Parse(p[0]), int.Parse(p[1])));
}
int accepted = 0;
int lastEnd = 0;
foreach (var booking in bookings.OrderBy(b => b.End))
{
if (booking.Start >= lastEnd)
{
accepted++;
lastEnd = booking.End;
}
}
Console.WriteLine(accepted);
Why it works
This is the exchange argument behind greedy interval scheduling. Among all bookings, the one that finishes first can always be part of some optimal answer: if an optimal answer used a different first booking, swapping in the earliest-ending one frees at least as much of the day and cannot clash with anything that came later. Applying that choice repeatedly gives the maximum. OrderBy(b => b.End) does the sort in one line, and the loop needs only the end hour of the last accepted booking. The comparison Start >= lastEnd rather than > is what allows back-to-back bookings, which the touching test cases exercise. The tuple list (int Start, int End) keeps the pairs together without writing a class.