Show problems as
Classic problem #3480HardArraySegment TreeEnumerationPrefix Sum

Maximize Subarrays After Removing One Conflicting Pair

Real-world version: Striking Out One Clash to Free the Most Stretches
Tracked in this browser only
Read Maximize Subarrays After Removing One Conflicting Pair on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Bins stand in a row numbered 1 through n. Each entry of clashes names two different bins that must never both lie inside a chosen stretch, where a stretch is any run of neighbouring bins.

Exactly one entry of clashes must be struck out. After that, count the non-empty stretches that hold no surviving entry's two bins together.

Return the largest count that striking out a single entry can leave.

Examples

Example 1

Input
n = 3, clashes = [[1, 2], [2, 3]]
Output
4

Whichever entry goes, one clash survives and rules out two of the six stretches, so four are left either way.

Example 2

Input
n = 2, clashes = [[1, 2]]
Output
3

Striking out the only entry leaves no clash at all, so all three stretches of the two bins count.

Example 3

Input
n = 2, clashes = [[1, 2], [1, 2]]
Output
2

Both entries name the same two bins, so striking one still leaves the other, and the single stretch covering both bins is ruled out.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_subarrays(n: int, clashes: list[list[int]]) -> int:
Java
public long maxSubarrays(int n, int[][] clashes)

More on the same topics