Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
UnionOfIntervals – SRM 277
public class UnionOfIntervals {
public static void main(String[] args){
UnionOfIntervals intervals = new UnionOfIntervals();
System.out.println(intervals.nthElement(new int[]{1,5},new int[]{3,7},4));
System.out.println(intervals.nthElement(new int[]{1,3},new int[]{4,5},3));
System.out.println(intervals.nthElement(new int[]{-1500000000},new int[]{1500000000},1500000091));
}
int nthElement(int[] lowerBound, int[] upperBound, int n){
long low, high;
low=1<<30;
for(long l: lowerBound){ if(l<low) low=l; }
high=0;
for(long u: upperBound){ if(high<u) high=u; }
while(low<high){
long mid = low+(high-low)/2;
long s=0;
for(int m=0;m<lowerBound.length;m++){
if(lowerBound[m]<mid){
if(mid<upperBound[m]){
s+=mid-lowerBound[m]+1;
}
else{
s+=upperBound[m]-lowerBound[m]+1;
}
}
}
System.out.printf("%d,%d,%d,%d\n",low,mid,high,s);
if(n<s) high = mid;
else low = mid+1;
}
return (int)low;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment