UnionOfIntervals – SRM 277

UnionOfIntervals.java

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;
    }
}