Problem statement

https://binarysearch.com/problems/Minimize-Maximum-Stadium-Size/

Solution

Let us fix x and use only nodes with weight > x. Then we can try to create bipartite graph, do it with dfs. Then use binary search to find the smallest x.

Complexity

It is O(E * log N) for time and O(E) for space, where E = len(views) and N is the biggest value of weight.

Code

class Solution:
    def isBipartite(self, G, n):
        def dfs(start):
            if self.loop: return

            for neib in G[start]:
                if dist[neib] >= 0 and dist[neib] == dist[start]:
                    self.loop = True
                elif dist[neib] < 0:
                    dist[neib] = dist[start]^1
                    dfs(neib)
            
        self.loop, dist = 0, [-1] *(n)
        
        for i in range(n):
            if self.loop: return False
            if dist[i] == -1:
                dist[i] = 0
                dfs(i)
                
        return True

    def solve(self, n, views):
        beg, end = 0, 10**9
        while beg + 1 < end:
            mid = (beg + end)//2
            G = defaultdict(list)
            for x, y, t in views:
                if t >= mid:
                    G[x] += [y]
                    G[y] += [x]

            if self.isBipartite(G, n):
                end = mid
            else:
                beg = mid

        return beg