Maximize Subarrays After Removing One Conflicting Pair - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3480. Maximize Subarrays After Removing One Conflicting Pair
Hard
50 Points
Array
Segment Tree
Enumeration
Prefix Sum
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 pair [a, b].
Return the maximum number of subarrays possible after removing exactly one conflicting pair.
Examples
Example 1
Input: n = 4, conflictingPairs = [[2,3],[1,4]]
Output: 9
Explanation:
Example 2
Input: n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
Output: 12
Explanation:
Constraints
2 <= n <= 105
1 <= conflictingPairs.length <= 2 * n
conflictingPairs[i].length == 2
1 <= conflictingPairs[i][j] <= n
conflictingPairs[i][0] != conflictingPairs[i][1]
3480. Maximize Subarrays After Removing One Conflicting Pair
Hard
50 Points
Array
Segment Tree
Enumeration
Prefix Sum
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 pair [a, b].
Return the maximum number of subarrays possible after removing exactly one conflicting pair.
Examples
Example 1
Input: n = 4, conflictingPairs = [[2,3],[1,4]]
Output: 9
Explanation:
Example 2
Input: n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
Output: 12
Explanation: