23.5. Greedy Strategy in Interval Scheduling

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.

This chunk introduces the problem of interval scheduling, which involves managing resources that can be booked over time. The key challenge here is that multiple requests for the same time period can overlap, meaning that only one booking can be honored at a time. The aim is to find a way to grant the maximum number of bookings possible without any overlaps.

Imagine you are managing a public park that people can reserve for parties. If two families want to book the park for overlapping times (like one family from 1 PM to 3 PM and another from 2 PM to 4 PM), only one can be allowed. Your goal is to accommodate as many reservations as possible.

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.

Once a booking is honored, any other overlapping bookings cannot be honored anymore since a resource can only be allocated to one event at a time. This leads to a sub problem where we focus on finding the next best booking to honor. The greedy strategy highlights choosing the booking with the earliest end time, as this will free up the resource sooner for potential future bookings.

Think about scheduling meetings. If you have a meeting that ends at 2 PM, and another that starts at 1:30 PM, you cannot accept both. By selecting the meeting that finishes earlier, you'll have more time to fit in additional meetings later in the day.

How many sub problems are there? Now, we have N bookings and every possible subset of this is a sub problem, so we have an exponential number of sub problems. In general, we have any possible subset could be our answer. So, we have to look through all these exponential things in principle in order to find the best allocation, the one that gives the maximum number of bookings to be satisfied. Now, what are greedy strategy does is effectively it cuts down this exponential space into a linear space, because what it does is it pick, so we have initially bookings 1 to N.

The theoretical complexity of this booking problem could lead to an exponential number of sub problems when considering every possible grouping of bookings. However, by applying a greedy approach (choosing the earliest finisher), the solution space is reduced significantly. Instead of checking every combination of bookings, we focus on a single ordering and solution set, effectively transforming the problem into a more manageable linear search space.

Imagine trying to find the best route for deliveries in a city with numerous stops. Checking every route possibility would take forever (exponential). However, if you decide to always pick the next stop that is closest to your current location (greedy), it becomes much easier to determine a workable route that minimizes time.

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.

In this variant of the problem, each request not only has a time frame but also a 'weight' or value associated with it, such as how much someone is willing to pay for the booking. The goal shifts from maximizing the number of bookings to maximizing the total weight (or total income generated). This change complicates the greedy strategy, as the previously simple choice of the earliest finish time may not yield the best financial outcome.

Consider a concert hall where different performers are willing to pay varying amounts to book the stage. Simply trying to fit in the most performances will not necessarily result in the highest income. You may have to prioritize a high-paying single performance over three low-paying ones.

So, the other approach which is what we are going to look at in more detail in the next few lectures is to try and look for an inductive solution which is obviously correct that which can be evaluated efficiently. So, the goal is to find to save, so what we are going to save is this effort in proving that by looking only at a few cases, we are actually producing an optimal answer. We would in some sense look at every case, but we look at every case in a clever way and that is what, we are going.

Instead of relying solely on the greedy strategy, which can overlook optimal solutions because of the rigid choice at each step, an inductive approach evaluates multiple scenarios without restricting the problem space too much. By exploring each possibility with care, this method aims to find the true optimal solution for bookings, especially when weights are involved.

Returning to the concert hall example, instead of just picking the next available artist, you might analyze all available combinations of artists and build a schedule that maximizes ticket sales, ensuring that even if some artists overlap, you still find the most profitable arrangement.

--