STADIUM - Editorial

editorial
1

Prerequisite :- Greedy, Sorting.

IARC Editorial :- IARC Editorial
Problem :- There is one sports stadium used by various organizations for their sports events. Each organization submits a request to the stadium manager, specifying the starting date and length of their event. The manager’s task is to allocate the stadium to maximize the number of events while ensuring there’s at least one gap day between any two events for cleaning.

For example, if the manager receives requests for four events starting on days 2, 9, 15, and 9 with lengths 5, 7, 6, and 3 days respectively, the manager can allocate the stadium for events starting on days 2, 9, and 15. This results in maximizing the number of events while ensuring no overlap.

The task is to help the manager find the maximum possible number of events that can use the stadium.

Explanation :-
Sorting Events in ascending order by End Date:

  • Start by arranging the events in the ascending order they end. This helps to process them in a way that makes sense in terms of time.
    Sorting the events based on their end times ensures that events with earlier end times are scheduled first. This allows the program to greedily select events with the earliest possible end times, maximizing the number of events that can be scheduled without overlapping.
  • By sorting in ascending order of end times, the program ensures that it considers events that end earlier before events that end later. This helps in maximizing the number of events scheduled without overlapping, as it leaves more time slots available for subsequent events.

Keeping Track of the Last Event:

  • Maintain a record of the last day an event was held in the stadium. This helps to ensure that there’s always a gap between consecutive events for cleaning purposes.

Counting Events:

  • Going through each event in increasing order, we check if there’s enough time between the end of the last event and the start of the current event.
  • If there’s enough time (i.e., no overlap), Hold the current event, and update the record of the last event.
  • Keep track of how many events one can hold without overlapping.

Outputing the Result:

  • Finally, we output the total number of events we can hold without any overlap. This tells us the maximum number of events that can be accommodated in the stadium.
  • In essence, the solution ensures that events are scheduled in a way that maximizes the use of the stadium while avoiding any conflicts or overlaps between events

C++ Solution : -

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector < pair < int, int >> v1;
  for (int i = 0; i < n; i++) {
    int n1, n2;
    cin >> n1 >> n2;
    v1.push_back({
      n1 + n2,
      n1
    });
  }
  sort(v1.begin(), v1.end());
  int last = 0;
  int cnt = 0;
  for (auto e: v1) {
    if (e.second > last) {
      cnt++;
      last = e.first;
    }
  }
  cout << cnt << "\n";
}