Challenge 04: Concurrent Events

Our beloved Ramzi needs your help! As the CSE director of undergraduate studies, he is in charge with scheduling numerous classes, meetings, and events for the faculty, staff, and students of the department. Given the limited amount of space the department has, it is often tricky to reserve the necessary classrooms or meeting spaces required for different events.

One particular problem Ramzi has in scheduling events is determining how many rooms he actually needs when there are possibly concurrent events. That is, when there are multiple events with overlapping time intervals, it can be difficult for him to determine exactly how many rooms he actually needs to reserve.

Therefore, he needs you to write a program that does the following:

Determine the maximum number of concurrent events given a series of time intervals.

For instance, suppose he had to arrange meeting spaces for the following events:

One way to solve this is by arranging the events graphically as shown below on the left. Once laid out in this manner, it becomes clear that there are two times where there are a maximum of 3 events happening at once. Therefore Ramzi would have to reserve three rooms for these concurrent events.

Because you are CSE students, however, Ramzi wants you to automate the process of determining the maximum number of concurrent events given a series of time intervals in software and he wants you to make sure it runs in O(nlogn) time (for each sequence of time intervals).

Input¶

You will be given a series of events in the following format:

N             # Number of events
Start1 Stop1  # Event 1 start and stop times
...
StartN StopN  # Event 1 start and stop times

That is, the first line contains N or the number of events in the test case, followed by N events which consist of a pair of start and stop times (integers).

Here is an example input:

4
1 3
2 4
3 5
4 6
4
2 4
1 5
1 3
2 6

This input corresponds to the example described above with an additional test case depicted above on the right.

Output¶

For each test case, output the maximum number of concurrent events for that test case as shown in the sample output below:

1. Maximum number of concurrent events is 3
2. Maximum number of concurrent events is 4

Be sure to prefix each line of output with the test case number (starting with 1).

Submission¶

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge04               # Create and checkout challenge04 branch

$ $EDITOR challenge04/program.cpp           # Edit your code

$ git add challenge04/program.cpp           # Stage your changes
$ git commit -m "challenge04: done"         # Commit your changes

$ git push -u origin challenge04            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge04 program.cpp ...
  Result Success
    Time 0.16
   Score 6.00 / 6.00

$ curl -F source=@challenge04/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge04
{"result": "Success", "score": 6, "time": 0.16451787948608398, "value": 6, "status": 0}