Help — Total number of unique integers in given n ranges

Revision en1, by go_rob, 2017-03-26 22:54:39

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)?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English go_rob 2017-03-26 22:54:39 517 Initial revision (published)