Highest Total Value from At Most k Non-Overlapping Meetings
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Each meeting has a start day, an end day and a value. You may attend at most `k` meetings, you must attend each chosen meeting from its start day through its end day, and you can attend only one meeting at a time. Return the largest total value you can collect.
### Function Signature
```python
def max_meeting_value(meetings: list[list[int]], k: int) -> int:
```
### Rules
- `meetings[i] = [start, end, value]` means meeting `i` occupies every day from `start` through `end`, both inclusive.
- Two meetings conflict when they share any day, so a meeting that ends on day `d` conflicts with a meeting that starts on day `d`.
- Choose at most `k` meetings, no two of which conflict, and return the largest possible sum of their values.
### Constraints
- `1 <= k <= len(meetings)` and `len(meetings) * k <= 10^6`
- `1 <= start <= end <= 10^9`
- `1 <= value <= 10^6`
- At most 1000 meetings can be chosen under these bounds, so the answer is at most `10^9`.
### Examples
**Example 1**
```text
Input: meetings = [[1, 2, 4], [2, 3, 6], [3, 4, 3]], k = 2
Output: 7
```
The meetings over days 1 to 2 and days 3 to 4 share no day, for 4 + 3 = 7. The value-6 meeting shares day 2 with the first meeting and day 3 with the third.
**Example 2**
```text
Input: meetings = [[1, 2, 4], [2, 3, 6], [3, 4, 3]], k = 1
Output: 6
```
With one meeting allowed, the most valuable one wins.
**Example 3**
```text
Input: meetings = [[1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 4, 4]], k = 3
Output: 9
```
No meetings conflict, so the three most valuable give 2 + 3 + 4 = 9.
Overview: Each meeting has a start day, an end day and a value, and meetings that share a day conflict; choose at most k meetings that do not conflict to maximize the total value. It tests interval scheduling with a count limit and building an efficient recurrence over sorted intervals.
You are given a list `meetings` where `meetings[i] = [start, end, value]`. Meeting `i` occupies every day from `start` through `end`, both inclusive, and attending it earns `value`. You may attend at most `k` meetings. Each chosen meeting must be attended from its start day through its end day, and you can attend only one meeting at a time.
Two meetings conflict when they share any day. In particular, a meeting that ends on day `d` conflicts with a meeting that starts on day `d`, while a meeting that ends on day `d` does not conflict with one that starts on day `d + 1`. The meetings may be given in any order, and the same meeting may appear more than once.
Choose at most `k` meetings, no two of which conflict, and return the largest possible sum of their values as a single integer.
Implement `max_meeting_value(meetings, k)`.
**Example 1**
Input: meetings = [[1, 2, 4], [2, 3, 6], [3, 4, 3]], k = 2
Output: 7
The meetings over days 1 to 2 and days 3 to 4 share no day, for 4 + 3 = 7. The value-6 meeting shares day 2 with the first meeting and day 3 with the third.
**Example 2**
Input: meetings = [[1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 4, 4]], k = 3
Output: 9
No meetings conflict, so the three most valuable give 2 + 3 + 4 = 9.
**Constraints**
- `1 <= k <= len(meetings)` and `len(meetings) * k <= 10^6`
- `1 <= start <= end <= 10^9`
- `1 <= value <= 10^6`
- At most 1000 meetings can be chosen under these bounds, so the answer is at most `10^9`. No input value or answer exceeds 2^31 - 1, so 32-bit signed integers suffice (Java `int`, C++ `int`).
Constraints
- 1 <= k <= len(meetings) and len(meetings) * k <= 10^6
- meetings[i] = [start, end, value] with 1 <= start <= end <= 10^9
- 1 <= value <= 10^6
- At most 1000 meetings can be chosen under these bounds, so the answer is at most 10^9 (it never exceeds 2^31 - 1)
Examples
Input: ([[1, 2, 4], [2, 3, 6], [3, 4, 3]], 2)
Expected Output: 7
Explanation: Source example 1: days 1-2 and 3-4 share no day, 4 + 3 = 7; the value-6 meeting conflicts with both.
Input: ([[1, 2, 4], [2, 3, 6], [3, 4, 3]], 1)
Expected Output: 6
Explanation: Source example 2: with one meeting allowed the most valuable one wins.
Hints
- A meeting that ends on day d and one that starts on day d share that day; only a meeting starting on day d + 1 or later can follow it.
- Taking a meeting rules out every meeting that overlaps it; think about which earlier choices are still available once you commit to it.
- You may use fewer than k meetings, and how many you have already used matters as much as the value collected so far.