Description
Solutions
TikTok Server Optimization
👩‍🎓 NEW GRAD

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].

Example 1:

Input:  numServers = 4, numDisconnectedPairs = 2, disconnectedPairs = [[1, 2], [2, 3]]
Output: 5
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:
    • 2 ≤ numServers ≤ 10^5
    • 0 ≤ numDisconnectedPairs ≤ 10^5
    • 1 ≤ numDisconnectedPairs count ≤ 10^5
    • 1 ≤ xi, yi ≤ numDisconnectedPairs.
    • xi != yi
Thumbnail 0
Testcase

Result
Case 1

input:

output: