hackercupai/hackercup huggingface dataset:
We'll maintain a set \(R\) of all "relevant" talk time intervals. An interval \([x, y]\) is considered irrelevant if ignoring it does not change the set of time intervals which may be proposed, which is the case if and only if there exists another interval which is inclusively contained within it (an interval \([x', y']\) such that \(x \le x'\) and \(y' \le y\)).

We'll maintain \(R\) ordered by intervals' start times, in strictly increasing order. Note that this also means that the intervals' end times must be strictly increasing (otherwise, they cannot all be relevant). For convenience, we'll also begin by including dummy intervals \([-1, -1]\) and \([K, K+1]\) in \(R\), whose significance is explained below. From there, updating the set for each new interval may be done relatively straightforwardly in amortized \(O(log(N))\) time, with the new interval either already being irrelevant, or being relevant and causing 0 or more existing intervals to become irrelevant.

What remains is maintaining the corresponding answer for \(R\) — that is, the number of time intervals which may be proposed without subsuming any interval in \(R\). For this purpose, let \(F([x_1, y_1], [x_2, y_2])\) be the number of different intervals \([x_p, y_p]\) which may be proposed such that \(x_1 < x_p \le x_2\), given that \([x_1, y_1]\) and \([x_2, y_2]\) form a pair of consecutive relevant intervals in \(R\). Note that \(F([x_1, y_1], [x_2, y_2])\) does not depend on any intervals in \(R\) besides those two, and may be easily computed in \(O(1)\) time using the fact that the only constraints are \(x_1 < x_p \le x_2\) and \(x_p < y_p < y_2\).

We can observe that the sum of \(F([x_1, y_1], [x_2, y_2])\) over all pairs of consecutive relevant intervals (of which there are \(|R| - 1\)) is equal to the total answer — for example, this is the case when \(R\) consists only of the initial pair of dummy intervals \([-1, -1]\) and \([K, K+1]\), with additional intervals simply partitioning the set of possible start times. We can then maintain this sum with no additional time complexity as we go. For example, when inserting an interval \(X\) between two existing intervals \(A\) and \(B\), we should increase the sum by \(F(A, X) + F(X, B) - F(A, B)\), with deletions handled similarly.

This gives us an algorithm with a time complexity of \(O(N log(N))\).