Peak Concurrent Chat Load From Agents' Inclusive Active Periods
Company: Cresta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a dictionary that maps each agent's id to the list of that agent's active periods. Each period is a triple `[start, end, chats]`: at every integer time `t` with `start <= t <= end` (both ends inclusive), that period contributes `chats` to the load. The load at time `t` is the sum of `chats` over all periods, from all agents, that contain `t`. Return the maximum load over all times, together with the earliest time at which that maximum occurs.
### Function Signature
```python
def peak_chat_load(agent_periods: dict[str, list[list[int]]]) -> list[int]:
```
### Rules
- Time takes integer values only, and the load is defined at every integer time.
- Both `start` and `end` belong to the period: a period `[3, 5, c]` adds `c` at times 3, 4 and 5.
- Periods of the same agent may overlap; every period counts separately.
- Return `[max_load, time]`, where `max_load` is the largest load at any time and `time` is the smallest integer time whose load equals `max_load`.
- An agent may have an empty list of periods.
### Constraints
- `1 <= number of agents <= 10^4`
- `1 <= total number of periods across all agents <= 10^5`
- `0 <= start <= end <= 10^9`
- `1 <= chats <= 10^4`
- Agent ids are non-empty strings.
- The maximum load is at most `10^9`, which fits in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: agent_periods = {"a1": [[1, 5, 2], [8, 10, 1]], "a2": [[3, 9, 3]]}
Output: [5, 3]
```
The load is 2 at times 1 and 2, 5 at times 3 to 5, 3 at times 6 and 7, 4 at times 8 and 9, and 1 at time 10. The maximum 5 first occurs at time 3.
**Example 2**
```text
Input: agent_periods = {"a1": [[1, 3, 2]], "a2": [[3, 4, 5]]}
Output: [7, 3]
```
Both periods include time 3, because each end is inclusive, so the load there is `2 + 5 = 7`.
**Example 3**
```text
Input: agent_periods = {"a1": [[4, 6, 3], [10, 12, 4]], "a2": [[1, 2, 4]], "a3": []}
Output: [4, 1]
```
The load reaches 4 at times 1 and 2 and again at times 10 to 12; the earliest of these is 1.
Overview: A coding question that gives each agent's active periods as inclusive start and end times with a chat count, and asks for the highest total load across all agents and the earliest time it occurs. It tests interval processing over large time ranges, inclusive boundaries and tie handling.
Read the full Cresta Software Engineer interview experience this question came from
You are given a dictionary `agent_periods` that maps each agent's id to the list of that agent's active periods. Each period is a triple `[start, end, chats]`: at every integer time `t` with `start <= t <= end` (both ends inclusive), that period contributes `chats` to the load. The load at time `t` is the sum of `chats` over all periods, from all agents, that contain `t`.
Return the list `[max_load, time]`, where `max_load` is the largest load at any integer time and `time` is the smallest integer time whose load equals `max_load`.
### Rules
- Time takes integer values only, and the load is defined at every integer time.
- Both `start` and `end` belong to the period: a period `[3, 5, c]` adds `c` at times 3, 4 and 5.
- Periods of the same agent may overlap; every period counts separately.
- An agent may have an empty list of periods.
### Example 1
```text
Input: agent_periods = {"a1": [[1, 5, 2], [8, 10, 1]], "a2": [[3, 9, 3]]}
Output: [5, 3]
```
The load is 2 at times 1 and 2, 5 at times 3 to 5, 3 at times 6 and 7, 4 at times 8 and 9, and 1 at time 10. The maximum 5 first occurs at time 3.
### Example 2
```text
Input: agent_periods = {"a1": [[1, 3, 2]], "a2": [[3, 4, 5]]}
Output: [7, 3]
```
Both periods include time 3, because each end is inclusive, so the load there is 2 + 5 = 7.
### Constraints
- `1 <= number of agents <= 10^4`
- `1 <= total number of periods across all agents <= 10^5`
- `0 <= start <= end <= 10^9`
- `1 <= chats <= 10^4`
- Agent ids are non-empty strings (in this console: printable ASCII, at most 20 characters).
- The maximum load is at most `10^9`, which fits in a signed 32-bit integer.
Neither returned value can exceed 2^31 - 1: both `max_load` and `time` are at most 10^9, so 32-bit integers hold the result.
Constraints
- 1 <= number of agents <= 10^4
- 1 <= total number of periods across all agents <= 10^5
- 0 <= start <= end <= 10^9
- 1 <= chats <= 10^4
- Agent ids are non-empty strings (in this console: printable ASCII, at most 20 characters)
- An agent's list of periods may be empty
- The maximum load is at most 10^9, which fits in a signed 32-bit integer
Examples
Input: ({'a1': [[1, 5, 2], [8, 10, 1]], 'a2': [[3, 9, 3]]},)
Expected Output: [5, 3]
Explanation: Source example 1: the load is 5 at times 3 to 5, first reached at time 3.
Input: ({'a1': [[1, 3, 2]], 'a2': [[3, 4, 5]]},)
Expected Output: [7, 3]
Explanation: Source example 2: inclusive ends make the periods overlap at time 3, load 2 + 5 = 7.
Hints
- Times go up to 10^9, so checking every integer time one by one is too slow; think about at which times the load can actually change.
- Both ends are inclusive: a period [start, end, chats] still counts at time end and stops counting only at time end + 1.
- Several separate stretches of time can share the maximum load; the answer is the smallest such time, regardless of the order in which agents or periods are listed.