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:

Event Start Stop
Operating System Principles 1 3
Theory of Computing 2 4
Computer Architecture 3 5

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.

Separate Rooms¶

While it is tempting to schedule the same room for back-to-back events such as in the intervals `(1, 3)` and `(3, 5)`, as you all know, it takes some time for people to both enter and leave a room. Therefore, events that start at the same time as another event ends would require a separate room to accommodate the flow of traffic. That is why the test case on the left requires `3` rooms instead of `2`.

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`).

Programming Challenges¶

This problem is inspired by "Problem 14.5" in Elements of Programming Interviews.

Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(E*log(E))`, where `E` is the number of events. Space Complexity `O(1)`

Your solution may be below the targets, but it should not exceed them.

Submission¶

``````\$ 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 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}
``````

Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 02 TA List.