aboutsummaryrefslogtreecommitdiff
path: root/max_employees_invited.py
blob: 5f28fb8c0b74cdd178b327782b61ba1e06d3b909 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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]))