Peak Capacity Overlapping Events (Line Sweep)

Maximum Concurrent Demand and Peak Intervals Medium · Line Sweep, Sorting, Intervals · Company Tags · Hints

You are given a set of tasks, each defined by a start time, an end time, and a resource demand (a positive integer). All tasks consume the resource continuously from their start time (inclusive) to their end time (exclusive). At any moment, the total resource usage is the sum of the demands of all tasks that are active at that moment.

Your task is to solve the following two parts:

1. Compute the maximum total resource usage that occurs at any point in time, denoted as peak.
2. Identify every maximal time interval during which the total usage is exactly peak. Return these intervals as a list of [start, end) pairs, sorted by start time, with no overlaps.

Input format:

• The first line contains an integer n (number of tasks).
• Each of the next n lines contains three integers: start, end, demand.

Output format:

• The first line: the integer peak.
• The second line: the integer k (number of peak intervals).
• Each of the next k lines: two integers representing the start and end of a peak interval.

Example 1:

Input:
3
1 4 5
2 5 3
3 6 2

Output:
10
1
3 4

Explanation: At time 3, all three tasks are active (demands 5+3+2=10), achieving the peak. This peak lasts from time 3 to 4 (when the first task ends). Hence the interval [3, 4).

Example 2:

Input:
4
1 3 5
2 4 2
5 7 3
6 8 4

Output:
7
2
2 3
6 7

Explanation: The peak demand 7 appears in two separate periods: [2,3) (tasks 1 and 2) and [6,7) (tasks 3 and 4).

Example 3:

Input:
1
1 5 10

Output:
10
1
1 5

Explanation: Only one task; its demand is the peak, and the interval is its entire active duration.

Constraints:

• 1 <= n <= 200,000
• 1 <= start < end <= 10^9
• 1 <= demand <= 10^9
• All times are integers. A line-sweep approach with sorting is expected to pass within time limits.