Good Server Segments
MediumSliding Window · TikTok
Servers are numbered 1 through num_servers in a row. Each entry [a, b] of disconnected_pairs says servers a and b cannot be placed in the same segment.
A segment is a contiguous range of servers [left, right] with 1 <= left <= right <= num_servers. A segment is good if, for every pair [a, b], it does not contain both a and b.
Return the number of good segments.
Pairs may be listed with either server first, and the same pair may appear more than once.
Example 1
- Input:
- num_servers = 5, disconnected_pairs = [[4, 2], [3, 5]]
- Output:
- 10
- Explanation
- There are 15 segments in total. Any segment containing both 2 and 4 is bad (
[1,4],[1,5],[2,4],[2,5]), and so is any containing both 3 and 5 ([3,5]plus the already counted[1,5],[2,5]). That removes 5 segments, leaving 10.
Example 2
- Input:
- num_servers = 4, disconnected_pairs = []
- Output:
- 10
- Explanation
- Every one of the 4 * 5 / 2 = 10 segments is good.
Example 3
- Input:
- num_servers = 6, disconnected_pairs = [[1, 6], [2, 3]]
- Output:
- 13
- Explanation
- The pair
[2, 3]is adjacent, so it rules out every segment that starts at 1 or 2 and ends at 3 or later (2 * 4 = 8 segments). The only segment holding both 1 and 6 is[1, 6], which is already among those. 21 - 8 = 13.
Constraints
1 <= num_servers <= 10^50 <= disconnected_pairs.length <= 2 * 10^51 <= a, b <= num_serversanda != b