aboutsummaryrefslogtreecommitdiff
path: root/max_subarr_remove_conflict_pair.py
blob: ad322b07087cc217a68bf2c9c10e18eecf34236b (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
# 3480. Maximize Subarrays After Removing One Conflicting Pair

"""
you are given an integer 'n' which represents an array 'nums' containing the
numbers from 1 to 'n' in order. additionally, you are given a 2d array
'conflictingPairs' where 'conflictingPairs[i] = [a, b]' indicates that 'a'
and 'b' form a conflicting pair. remove exactly one element from
'conflictingPairs'. afterward, count the number of non-empty subarrays of
'nums' which do not contain both 'a' and 'b' for any remaining conflicting
pairs '[a, b]'. return the maximum number of subarrays possible after
removing exactly one conflicting pair.
"""


class Solution(object):
    def maxSubarrays(self, n, conflictingPairs):
        """
        :type n: int
        :type conflictingPairs: List[List[int]]
        :rtype: int
        """
        right = [[] for _ in range(n + 1)]
        for a, b in conflictingPairs:
            right[max(a, b)].append(min(a, b))
        ans, left = 0, [0, 0]
        s = [0] * (n + 1)
        for r in range(1, n + 1):
            for l in right[r]:
                left = max(left, [l, left[0]], [left[0], l])
            ans += r - left[0]
            s[left[0]] += left[0] - left[1]
        return ans + max(s)


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxSubarrays(n=4, conflictingPairs=[[2, 3], [1, 4]]))
    print(obj.maxSubarrays(n=5, conflictingPairs=[[1, 2], [2, 5], [3, 5]]))