aboutsummaryrefslogtreecommitdiff
path: root/max_employees_invited.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_employees_invited.py')
-rw-r--r--max_employees_invited.py61
1 files changed, 61 insertions, 0 deletions
diff --git a/max_employees_invited.py b/max_employees_invited.py
new file mode 100644
index 0000000..5f28fb8
--- /dev/null
+++ b/max_employees_invited.py
@@ -0,0 +1,61 @@
+# 2127. Maximum Employees to Be Invited to a Meeting
+from collections import defaultdict, deque
+
+"""
+a company is organising a meeting and has a list of 'n' employees, waiting to
+be invited. they have arrange for a large circular table, capable of seating
+any number of employees. the employees are numbered from 0 to 'n - 1'. each
+employee has a favourite person and they will attend the meeting only if they
+can sit next to their favourite person. the favourite person of an employee
+is not themselves. given a 0 indexed integer array 'favorite' where
+'favorite[i]' denotes the favourite person of the i'th employee, return the
+maximum number of employees that can be invited.
+"""
+
+
+class Solution(object):
+ def maximumInvitations(self, favorite):
+ """
+ :type favorite: List[int]
+ :rtype: int
+ """
+ indegrees = defaultdict(list)
+ for idx, fav in enumerate(favorite):
+ indegrees[fav].append(idx)
+
+ def bfs(start, seen):
+ q, res = deque([(start, 0)]), 0
+ while q:
+ pos, dist = q.popleft()
+ for i in indegrees[pos]:
+ if i in seen:
+ continue
+ seen.add(i)
+ q.append((i, dist + 1))
+ res = max(res, dist + 1)
+ return res
+
+ n = len(favorite)
+ cycle_largest, cycle_sum = 0, 0
+ for i in range(n):
+ if favorite[i] != -1:
+ dist = {i: 0}
+ while favorite[i] != -1:
+ next = favorite[i]
+ favorite[i] = -1
+ if next in dist:
+ cycle_len = len(dist) - dist[next]
+ cycle_largest = max(cycle_largest, cycle_len)
+ if cycle_len == 2:
+ cycle_sum += 2 + bfs(next, {i, next}) + bfs(i, {i, next})
+ else:
+ i = next
+ dist[next] = len(dist)
+ return max(cycle_largest, cycle_sum)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumInvitations(favorite=[2, 2, 1, 2]))
+ print(obj.maximumInvitations(favorite=[1, 2, 0]))
+ print(obj.maximumInvitations(favorite=[3, 0, 1, 4, 1]))