We are given n ranges `(L1,R1) , (L2,R2) , ... .. (Ln,Rn)'
All ranges are integer values between (0 to 10^6). We have to find out the total number of unique integers across all the ranges?
Ex. For n = 3, (1,4) , (2,3) , (4,5) the answer is 5.
My solution is to sort the ranges according to their L value and then iterate one by one using two pointers. Time Complexity O(n*Log(n)).
Is there any better solution than this(may be using Hash Maps)?
Since you said that the ranges are from 0 to 10^6, then you can use the +1, -1 trick. The trick is as follows: First maintain an array of size 10^6+2, then, for each query L,R, you do this: {ar[L]++; ar[R+1]--;}, now after answering all queries, find the prefix sum array of ar till index = max of all R values, the no. of non-zero entries in this prefix sum array is your answer. The complexity is O(n+Q) where n<=10^6 and Q is the total no. of queries.
This won't be correct. Consider 2 ranges (2,7) and (4,8). Here that method would count elements 3-7 twice and we only need to count each number once.EDIT : This comment was made before the revision of the parent comment. Please ignore this comment.
No bro, it seems like you misunderstood my soln., you need to find the no. of non-zero elements in the prefix sum array, not the prefix sum itself. So each element gets counted only once, if and only if it is non-zero.
I agree. My comment was made before you revised your answer to include that you only count the number of non zero elements and not their actual values.
I NEVER mentioned to take the prefix sum itself as the answer. You can go check my revision history :)
I know. I misunderstood your solution. My mistake. (Hence the +1 for your answers)
Here is +1 for accepting ur mistake :). Happy Coding!