Maximum Overlapping Workshops

You are given n workshops, each with a start day and an end day. A workshop is active during all days between its start and end day (inclusive). Your task is to determine the maximum number of workshops that are active on the same day.

The problem can be efficiently solved by using a sweep line algorithm. For each workshop interval \([l, r]\), consider two events: a start event at day \(l\) and an end event at day \(r + 1\) (to mark the end of the interval). By sorting these events and iterating through them while keeping track of the current number of active workshops, you can determine the maximum overlap.

Below is the detailed explanation:

• Input: An integer \(n\) on the first line followed by \(n\) lines where each line contains two integers \(l\) and \(r\) representing a workshop's start and end days.
• Process: For every workshop, add an event \((l, +1)\) and an event \((r+1, -1)\). After sorting these events by day, update a running counter by adding the event values and record the maximum value encountered.
• Output: Print the maximum number of overlapping workshops.

The algorithm is efficient even for large inputs due to its \(O(n \log n)\) time complexity from sorting.

inputFormat

The first line contains an integer n, the number of workshops.

Each of the next n lines contains two space-separated integers l and r representing the start and end day of a workshop.

outputFormat

Output a single integer representing the maximum number of overlapping workshops on any day.

3
1 5
2 6
3 7

3