3480. Maximize Subarrays After Removing One Conflicting Pair

Posted on Edited on In

3480. Maximize Subarrays After Removing One Conflicting Pair

Description

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 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.

Example 1:

1
2
3
Input: n = 4, conflictingPairs = [[2,3],[1,4]]

Output: 9

Explanation:

  • Remove [2, 3] from conflictingPairs. Now, conflictingPairs = [[1, 4]].
  • There are 9 subarrays in nums where [1, 4] do not appear together. They are [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 3] and [2, 3, 4].
  • The maximum number of subarrays we can achieve after removing one element from conflictingPairs is 9.

Example 2:

1
2
3
Input: n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]

Output: 12

Explanation:

  • Remove [1, 2] from conflictingPairs. Now, conflictingPairs = [[2, 5], [3, 5]].
  • There are 12 subarrays in nums where [2, 5] and [3, 5] do not appear together.
  • The maximum number of subarrays we can achieve after removing one element from conflictingPairs is 12.

Constraints:

  • 2 <= n <= 10^5
  • 1 <= conflictingPairs.length <= 2 * n
  • conflictingPairs[i].length == 2
  • 1 <= conflictingPairs[i][j] <= n
  • conflictingPairs[i][0] != conflictingPairs[i][1]

Hints/Notes

Solution

Language: C++

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
class Solution {
public:
    long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {
        vector<vector<int>> groups(n + 1);
        for (auto& p : conflictingPairs) {
            int a = p[0], b = p[1];
            if (a > b) {
                swap(a, b);
            }
            groups[a].push_back(b);
        }
        long long ans = 0;
        vector<long long> extra(n + 2);
        vector<int> b = {n + 1, n + 1}; // the most and second smallest b
        for (int a = n; a > 0; a--) {
            auto& list_b = groups[a];
            b.insert(b.end(), list_b.begin(), list_b.end());
            ranges::sort(b);
            b.resize(2);
            ans += b[0] - a;
            extra[b[0]] += b[1] - b[0];
        }
        return ans + ranges::max(extra);
    }
};