Problem Brief

TikTok Server Optimization

NEW GRADOA

See Tiktok online assessment and hiring insights

TikTok is organizing a grand TikTok event and wants to optimize the content delivery routes for the users. They have numServers servers numbered from 1 to numServers. The servers will be arranged in a sequence as follows: [1, 2, 3, ..., numServers]. The company has a list of numDisconnectedPairs pairs of servers that are not directly connected. Any pair not present in this list are directly connected. A subsegment of the route starting from server start and ending at server end is [start, start+1, start+2, ..., end]. A subsegment of the route is called good when all pairs of servers in that segment are directly connected. TikTok wants to know how many pairs (start, end) there are (1 ≤ start ≤ end ≤ numServers), such that the subsegment starting from server start and ending at server end is good.

Note: Servers can be reused across different subsegments. Each subsegment is considered independently, so a server can be part of multiple “good” subsegments. For example, if a server 3 is part of a “good” subsegment [2, 3, 4], it can still be reused in another “good” subsegment, like [3, 4, 5].

1Example 1

Input

numServers = 4, numDisconnectedPairs = 2, disconnectedPairs = [[1, 2], [2, 3]]

Output

Explanation

Disconnected Pairs:

(1, 2) are not directly connected. (2, 3) are not directly connected.

The good subsegments are:

[1]: Only one server, so it’s automatically “good”.
[2]: Only one server, so it’s automatically “good”.
[3]: Only one server, so it’s automatically “good”.
[4]: Only one server, so it’s automatically “good”.
[3, 4]: Both servers 3 and 4 are directly connected.

Constraints

Limits and guarantees your solution can rely on.

2 ≤ numServers ≤ 10^5
0 ≤ numDisconnectedPairs ≤ 10^5
1 ≤ numDisconnectedPairs count ≤ 10^5
1 ≤ xi, yi ≤ numDisconnectedPairs.
xi != yi