aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-25 21:30:58 -0700
committerJack Sangdahl <[email protected]>2025-01-25 21:30:58 -0700
commit61a53a0b0943dfdd717eb289139974f21a9ee459 (patch)
tree35d13a90e3078ad516e7fb2e217294b27f6f9c57
parent3c86d5ce6885144cf5db34e182066407191aea66 (diff)
downloadleetcode-61a53a0b0943dfdd717eb289139974f21a9ee459.tar.gz
leetcode-61a53a0b0943dfdd717eb289139974f21a9ee459.zip
2127. maximum employees to be invited to a meeting
-rw-r--r--max_employees_invited.c78
-rw-r--r--max_employees_invited.py61
2 files changed, 139 insertions, 0 deletions
diff --git a/max_employees_invited.c b/max_employees_invited.c
new file mode 100644
index 0000000..1537ae4
--- /dev/null
+++ b/max_employees_invited.c
@@ -0,0 +1,78 @@
+// 2127. Maximum Employees to Be Invited to a Meeting
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+void topo_sort(const int *favorite, int *indegrees, int *chain_lens, int *stack,
+ int node_cnt) {
+ int stack_idx = 0;
+ for (int i = 0; i < node_cnt; i++)
+ if (!indegrees[i])
+ stack[stack_idx++] = i;
+ while (stack_idx) {
+ int node = stack[--stack_idx], nn = chain_lens[node],
+ parent = favorite[node], pn = chain_lens[parent];
+ if (pn <= nn)
+ chain_lens[parent] = nn + 1;
+ indegrees[parent]--;
+ if (!indegrees[parent])
+ stack[stack_idx++] = parent;
+ }
+}
+
+int traverse(const int *favorite, int *unvis, const int *chain_lens,
+ int node_cnt) {
+ int largest = 0, sum = 0;
+ for (int i = 0; i < node_cnt; i++) {
+ if (!unvis[i])
+ continue;
+ int start = i, curr = i, cn = 0;
+ do {
+ unvis[curr] = 0;
+ cn++;
+ curr = favorite[curr];
+ } while (curr != start);
+ if (cn > 2)
+ largest = fmax(largest, cn);
+ else
+ sum += chain_lens[curr] + chain_lens[favorite[curr]] + 2;
+ }
+ return fmax(largest, sum);
+}
+
+int dfs(int *favorite, int favoriteSize) {
+ int *buf = (int *)malloc(3 * favoriteSize * sizeof(int));
+ int *indegrees = buf;
+ memset(indegrees, 0, favoriteSize * sizeof(int));
+ int *chain_lens = indegrees + favoriteSize;
+ memset(chain_lens, 0, favoriteSize * sizeof(int));
+ int *stack = chain_lens + favoriteSize;
+ for (int i = 0; i < favoriteSize; i++) {
+ int parent = favorite[i];
+ indegrees[parent]++;
+ }
+ topo_sort(favorite, indegrees, chain_lens, stack, favoriteSize);
+ int ans = traverse(favorite, indegrees, chain_lens, favoriteSize);
+ free(buf);
+ return ans;
+}
+
+int maximumInvitations(int *favorite, int favoriteSize) {
+ return dfs(&favorite[0], favoriteSize);
+}
+
+int main() {
+ int f1[] = {2, 2, 1, 2}, f2[] = {1, 2, 0}, f3[] = {3, 0, 1, 4, 1};
+ printf("%d\n", maximumInvitations(f1, ARRAY_SIZE(f1))); // expect: 3
+ printf("%d\n", maximumInvitations(f2, ARRAY_SIZE(f2))); // expect: 3
+ printf("%d\n", maximumInvitations(f3, ARRAY_SIZE(f3))); // expect: 4
+}
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]))