23.4. Interval Scheduling Problem

So, now let us look at a problem that we are seen before in the context of greedy algorithms. So, we will look at the problem called interval scheduling. So, integrated scheduling said that we had a resource which is available over a period of time and now people will come and make bookings for these resources. So, somebody may want to book it during this segment, somebody else may want to book it in this segment, somebody else may wanted it during these segment and so on.

Now, during these overlapping things, you cannot give the resource to two people, so you have given a set of request each for the starting time and an ending time. So, we have a start and an end or a finish time and now what you want to do is, decide which of these requests you can allocate, so that the maximum number of bookings are actually granted. So, the goal is to maximize the number of bookings not the length of the bookings, but the number of bookings.

The Interval Scheduling Problem involves scheduling resources for requests that have specific start and end times. The challenge arises when these requests overlap, meaning the same resource cannot be allocated to multiple requests at the same time. The goal is to maximize the number of accepted requests, rather than the duration of each booking. This is a common problem in resource management, like scheduling rooms or equipment where only one request can occupy the resource at a time.

Imagine you're managing a community center with one room available for events. You receive booking requests for various events, each with a start and end time. If two requests overlap, you can only accept one. Your task is to maximize the number of events hosted without double-booking the room. So if you have requests from 1 PM to 2 PM and 1:30 PM to 3 PM, you can only select one. If you choose the first request, you have more slots available after 2 PM for other potential bookings.

So, in this particular case, what happens is that when you honour a booking, now if a booking happens to be overlapping with few other bookings, then if I decided to take this booking, then this goes away. So, these two bookings which overlapped with it, it can no longer be scheduled, because they are conflict with this in sometime interval. So, therefore now we have to solve or find a way of allocating the remaining bookings for some subset of the problem of the bookings.

So, each subset of the bookings is a sub problem in this case and the strategy that we saw was a greedy one, which said to pick the one which has the earliest finishing time. So, among all those bookings which has still available to us to allocate, we pick one in a greedy way by just looking at it among all those are remain the earlier finishing time.

When dealing with overlapping booking requests, the strategy is to choose the request that finishes the earliest. This 'greedy' method is effective because selecting the earliest finishing request allows more future requests to be potentially accepted. Each decision leads to a sub-problem where you can consider the remaining requests that do not conflict with the selected one. This approach reduces the complexity of the problem significantly.

Think of it like a bus schedule where each bus arrives at a station for a short time. If a bus arrives at 1 PM and leaves by 1:30 PM, and another arrives at 1:15 PM and leaves at 1:45 PM, you can only accommodate one bus during that half-hour. By selecting the first bus, which leaves earlier, you leave more time for additional buses to schedule arrivals after 1:30 PM.

So, suppose we change the interval scheduling problem very slightly, we associate with each request a weight, a weight could be for example, the amount somebody is willing to pay, so may be people are trying to book, so we have an auditorium which we enter for performances and other activities. And people, who come to use it are willing to pay to use it. Of course, there is only one auditorium, so two people cannot use at the same time.

Now, our earlier goal was to maximize the number of bookings that we gave, but now, we have another criterion which is more immediate, which is how much each person is willing to pay. So, even if give to only one person, if that person is paying a lot more than everybody else and that would be optimum for us. So, now our aim is to maximize the total weight. So, we want to get as much revenue as possible from our allocation not the number of bookings, but the total weight.

In this variation of the interval scheduling problem, each request has an associated weight representing the value or profit of the booking (like how much a person is willing to pay). This changes the focus from merely maximizing the number of bookings to maximizing the total profit from the accepted bookings. It’s important to make strategic choices based on the weights to achieve the highest total revenue, which complicates the greedy strategy from before where only the earliest finish times were considered.

Consider an auction for a performance venue where different performers are interested in booking time slots. Each performer offers a different amount to rent the space. Booking the high-paying performer might yield more profit, even if it means scheduling fewer events. For instance, if one performer offers $500 to book an evening while three others offer$100 for their slots, accepting the $500 booking maximizes your revenue―showing that it's not always about number, but about the weight of value offered.

--