We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I solved this using two binary indexed trees, longest running time being 0.28s. Let [L1,R1], [L2,R2] be intervals, with L1 <= R1, L2 <= R2. To check whether they overlap or not, we simply check if ((R2 < L1) || (L2 > R1)) holds. If this is true, then they are NOT overlapping, otherwise they overlap.
Let the set of all N intervals be given, say [A1,B1] ... [AN,BN], for each player interval [C,D] we want to count the number of NON-overlapping intervals from [Ai,Bi]'s, then the overlap count can be incremented by (N - (non-overlapping count)). We can use a binary indexed tree to preprocess the [Ai,Bi]'s to store the number of Bi's occurred BEFORE a given position, and another BIT tree for the number of Ai's occurring AFTER a given position.
Then, when the player interval [C,D] is given, simply use the BIT trees above to determine the number of Ai's greater then D, and the number of Bi's less then C.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Mr. X and His Shots
You are viewing a single comment's thread. Return to all comments →
I solved this using two binary indexed trees, longest running time being 0.28s. Let [L1,R1], [L2,R2] be intervals, with L1 <= R1, L2 <= R2. To check whether they overlap or not, we simply check if ((R2 < L1) || (L2 > R1)) holds. If this is true, then they are NOT overlapping, otherwise they overlap.
Let the set of all N intervals be given, say [A1,B1] ... [AN,BN], for each player interval [C,D] we want to count the number of NON-overlapping intervals from [Ai,Bi]'s, then the overlap count can be incremented by (N - (non-overlapping count)). We can use a binary indexed tree to preprocess the [Ai,Bi]'s to store the number of Bi's occurred BEFORE a given position, and another BIT tree for the number of Ai's occurring AFTER a given position.
Then, when the player interval [C,D] is given, simply use the BIT trees above to determine the number of Ai's greater then D, and the number of Bi's less then C.