Max Level Party Invites
## description
## Max Level Party Invites
You are given a list of n employees each assigned a level between 0 and 10. The employees and their levels are represented as an array of integers, levels, where the index, i, is the employee's identifier and the value levels[i] is their level.
You are also provided a reporting_chain which represents the reporting structure of employees where each entries first value is the manager and the second value in that entry is their direct report.
For example, a reporting_chain that consists of [[0, 1], [0, 2], [1, 3]] would indicate:
Employee 0 manages Employee 1 Employee 0 manages Employee 2 Employee 1 manages Employee 3
You are tasked with inviting people from this company to a party, however, the constraint is the if an employee is invited, none of their direct reports can be invited.
Following this constraint, return the max sum of levels possible given a selection of employees to invite.
Example 1:
1Input: levels = [10, 9, 9, 5, 5, 5, 6], reporting_chain = [[0, 1], [0,2], [1, 3], [1, 4], [1, 5], [2, 6]]
2Output: 31
3Explanation: If we invite 0 (level 10), employee 1 (level 9) and 2 (level 9) cannot be invited. Inviting the rest is fine and thus the best sum is 31.Example 2:
1Input: levels = [8, 6, 7, 4, 5], reporting_chain = [[0, 1], [1, 2], [2, 3], [3, 4]]
2Output: 20
3Explanation: Invite 0, 2, 4. Skip 1, 3.Example 3:
1Input: levels = [10, 9], reporting_chain = [[0, 1]]
2Output: 10
3Explanation: No other employees## notes
### Intuition
This is a tree DP problem similar to "House Robber III." For each employee, we compute two values: the maximum sum if we invite them (must skip their direct reports) and if we skip them (can choose either for reports).
### Implementation
Build an adjacency list from the reporting chain and identify root employees (those without managers). DFS with memoization computes (invite, skip) pairs bottom-up. If we invite an employee, add their level plus the skip values of all reports. If we skip, add max(invite, skip) of each report. Process all roots and sum the maximum of invite/skip for each tree.
### Edge-cases
The graph may be a forest (multiple disconnected trees). Track which nodes have parents to identify all roots and process each independently.
- –Time: O(n) — each node processed exactly once via memoization
- –Space: O(n) — adjacency list and memoization cache
### Complexity
## solution
1from typing import List, Tuple, Dict
2from collections import defaultdict
3
4class Solution:
5 def maxLevelPartyInvites(self, levels: List[int], reporting_chain: List[List[int]]) -> int:
6 n = len(levels)
7 reports = defaultdict(list)
8 # Create adjacency list and mark parents to extract roots later
9 has_parent = [False] * n
10 for manager, report in reporting_chain:
11 reports[manager].append(report)
12 has_parent[report] = True
13
14
15 memo: Dict[int, Tuple[int, int]] = {}
16 def dfs(employee: int) -> Tuple[int, int]:
17 if employee in memo:
18 return memo[employee]
19
20 invite_employee = levels[employee]
21 skip_employee = 0
22 for report in reports[employee]:
23 invite_report, skip_report = dfs(report)
24 invite_employee += skip_report # if u is invited, sum if v is not invited (skip_v)
25 skip_employee += max(invite_report, skip_report) # if u is skipped, we can choose to invite v or not
26
27 memo[employee] = (invite_employee, skip_employee)
28 return memo[employee]
29
30 # Only start DFS on roots because otherwise we can miss nodes or double count them
31 root_employees = [i for i in range(n) if not has_parent[i]]
32 total = 0
33 for root_employee in root_employees:
34 invite, skip = dfs(root_employee)
35 total += max(invite, skip)
36 return total;
37
38if __name__ == "__main__":
39 # Include one-off tests here or debugging logic that can be run by running this file
40 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
41 solution = Solution()
42