Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a right endpoint r, every conflict whose larger endpoint is at most r forces the subarray's start past its smaller endpoint. The largest such lower bound determines the valid count. Removing its uniquely responsible conflict relaxes that bound only as far as the second-largest bound.

Approach

Normalize every conflicting pair and group its smaller endpoint by its larger endpoint. Sweep r from one through n, adding newly active bounds while retaining the largest and second-largest values, including ties. Add r - largest to the count with all conflicts present.

Also accumulate the potential gain largest - secondLargest under the largest bound's value. Tied largest bounds yield zero gain because removing one leaves the other. Grouping gains by endpoint is sufficient: after a second conflict with the same smaller endpoint becomes active, it remains active forever, so that endpoint cannot later earn a positive gain for a different conflict.

Return the baseline count plus the largest accumulated gain. Each subarray is counted at its right endpoint, and the chosen gain represents removing one conflict consistently across the whole sweep.

class Solution:
    def maxSubarrays(self, n: int, conflictingPairs: List[List[int]]) -> int:
        limits = defaultdict(list)
        for a, b in conflictingPairs:
            limits[max(a, b)].append(min(a, b))

        res = 0
        left = [0, 0]
        after_removal = [0] * (n + 1)
        for r in range(1, n + 1):
            for l in limits[r]:
                # left = max(left, [left[0], l], [l, left[0]]) # [larges, second largest]
                if l > left[0]:
                    left[1] = left[0]
                    left[0] = l
                elif l > left[1]:
                    left[1] = l
            res += r - left[0]
            after_removal[left[0]] += left[0] - left[1]

        return res + max(after_removal)

Complexity analysis

Let n be the permutation size and q = conflictingPairs.length. Time: O(n + q). Auxiliary space: O(n + q).