Let’s read the problem as follows:

“There are \(N\) users. The \(i\)-th user logged in at time \(L_i\) and logged out at time \(R_i\). Find the intervals of times during which at least one user was online.”

Below, we consider the problem above.

In order to answer this question, it is sufficient to find the time when the online count changes from \(0\) to \(1\), and when it changes from \(1\) to \(0\).

This problem can be solved by sorting \(L_i\) and \(R_i\) at once and simulating the transition of online count by login/logout in order. Note that, if one user logs in and another logs out at the same time, the login should be processed first. The time complexity is \(O(N\log N)\).

Sample code (C++)

This problem can be solved with cumulative sums in a total of \(O(N+\max R_i)\) time.

Sample code (C)