3480. Maximize Subarrays After Removing One Conflicting Pair

 C++

class Solution {

 public:

  long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {

    long validSubarrays = 0;

    int maxLeft = 0;

    int secondMaxLeft = 0;

   

    vector<long> gains(n + 1);

    vector<vector<int>> conflicts(n + 1);

    for (const vector<int>& pair : conflictingPairs) {

      const int a = pair[0];

      const int b = pair[1];

      conflicts[max(a, b)].push_back(min(a, b));

    }

    for (int right = 1; right <= n; ++right) {

      for (const int left : conflicts[right]) {

        if (left > maxLeft) {

          secondMaxLeft = maxLeft;

          maxLeft = left;

        } else if (left > secondMaxLeft) {

          secondMaxLeft = left;

        }

      }

   

      validSubarrays += right - maxLeft;

     

     

      gains[maxLeft] += maxLeft - secondMaxLeft;

    }

    return validSubarrays + ranges::max(gains);

  }

};

JAVA

class Solution {

  public long maxSubarrays(int n, int[][] conflictingPairs) {

    long validSubarrays = 0;

    int maxLeft = 0;

    int secondMaxLeft = 0;

    long[] gains = new long[n + 1];

   

    List<Integer>[] conflicts = new List[n + 1];

    for (int i = 0; i <= n; ++i)

      conflicts[i] = new ArrayList<>();

    for (int[] pair : conflictingPairs) {

      final int a = pair[0];

      final int b = pair[1];

      conflicts[Math.max(a, b)].add(Math.min(a, b));

    }

    for (int right = 1; right <= n; ++right) {

      for (int left : conflicts[right]) {

        if (left > maxLeft) {

          secondMaxLeft = maxLeft;

          maxLeft = left;

        } else if (left > secondMaxLeft) {

          secondMaxLeft = left;

        }

      }

     

      validSubarrays += right - maxLeft;

      gains[maxLeft] += maxLeft - secondMaxLeft;

    }

    return validSubarrays + Arrays.stream(gains).max().getAsLong();

  }

}