9-7: 구간의 합집합

구간의 합집합 (union.cpp)

 

문제

---

구간은 [s, e] 로 나타내고, 이 의미는 s, (s+1), (s+2), …, (e-1), e 와 같이 숫자를 나열한 것을 의미한다. 예를 들어, [1, 4]는 1, 2, 3, 4로 숫자를 나열한 것을 의미한다. n개의 구간이 있고, 이 구간들의 숫자를 모두다 새로운 배열 S에 넣어 정렬을 한다. 이 때 S[i] 의 값이 무엇인지 출력하는 프로그램을 작성하시오. 예를 들어, 3개의 구간 [1, 3], [2, 10], [1, 8] 이 있고, S[5]를 알고싶다고 하자. 그러면 S = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 10] 이 되고, 따라서 S[5]는 3이 된다. 배열의 인덱스는 0부터 시작한다는 것에 주의하자.

 

입력

---

첫 번째 줄에 구간의 개수 n이 주어진다 ( 1 ≤ n ≤ 10,000 ) 두 번째 줄부터 각 구간을 나타내는 숫자 s, e가 주어진다. ( 1 ≤ s ≤ e ≤ 1,000,000,000 ) 그 후, 마지막 줄에는 값을 알고 싶은 숫자의 위치 i가 주어진다. ( 1 ≤ i ≤ 10,000,000,000,000 ) i번째 위치에는 항상 숫자가 존재한다고 가정한다.  

출력

---

S[i]를 출력한다.  

예제 입력

2
1 4
3 5
3

예제 출력

3

예제 입력

3
1 3
2 10
1 8
5

예제 출력

3

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class union {

    /**
     *
     * 문제: 구간은 [s, e] 로 나타내고, 이 의미는 s, (s+1), (s+2), …, (e-1), e 와 같이 숫자를 나열한 것을 의미한다.
     * 예를 들어, [1, 4]는 1, 2, 3, 4로 숫자를 나열한 것을 의미한다. n개의 구간이 있고, 이 구간들의 숫자를 모두다 새로운 배열 S에 넣어 정렬을 한다.
     * 이 때 S[i] 의 값이 무엇인지 출력하는 프로그램을 작성하시오. 예를 들어, 3개의 구간 [1, 3], [2, 10], [1, 8] 이 있고, S[5]를 알고싶다고 하자.
     * 그러면 S = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 10] 이 되고, 따라서 S[5]는 3이 된다. 배열의 인덱스는 0부터 시작한다는 것에 주의하자.
     *
     *
     * 입력:
     *
     * 첫 번째 줄에 구간의 개수 n이 주어진다 ( 1 ≤ n ≤ 10,000 ) 두 번째 줄부터 각 구간을 나타내는 숫자 s, e가 주어진다. ( 1 ≤ s ≤ e ≤ 1,000,000,000 )
     * 그 후, 마지막 줄에는 값을 알고 싶은 숫자의 위치 i가 주어진다. ( 1 ≤ i ≤ 10,000,000,000,000 ) i번째 위치에는 항상 숫자가 존재한다고 가정한다.
     *
     * 출력: S[i]를 출력한다.
     *
     *
     * 예제 입력:
     *
     * 2
     * 1 4
     * 3 5
     * 3
     *
     *
     * 예제 출력:
     * 3
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long bounds[][] = new long[N][2];

        long max = 0, min = Long.MAX_VALUE;
        for (int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            bounds[i][0] = Long.parseLong(st.nextToken());
            bounds[i][1] = Long.parseLong(st.nextToken());
            if (max < bounds[i][1]){
                max = bounds[i][1];
            }
            if (min > bounds[i][0]){
                min = bounds[i][0];
            }

        }

        long i = Long.parseLong(br.readLine());
        if (debug) System.out.println("targetIndex: " + i);


        long result = binarySearch(min, max, bounds, i);
        System.out.print(result);
    }

    //        private static boolean debug = true;
    private static boolean debug = false;

    private static long binarySearch(long start, long end, long[][] bounds, long targetIndex){
        while (start <= end){
            if (debug) System.out.println("\nstart: " + start+ ", end: " + end);
            long mid = (start + end) /2;
            //assume mid is target number
            if (debug) System.out.println("mid: " + mid);

            //for each bound, check if bound contains mid. compute index from start.
            //find index range for element mid.

            long index = 0;
            long midContainCount = 0;


            for (int i=0; i<bounds.length; i++){
                long upper= bounds[i][1];
                long lower = bounds[i][0];
                if (debug) System.out.println("bound's lower: " + lower+ ", upper: " + upper);
                if (mid <= upper && mid>= lower){
                    if (debug) System.out.println("element " + mid +" is between lower and upper, add index by " + (mid - lower));
                    index+= mid - lower;
                    midContainCount++;
                } else if (mid > upper){
                    if (debug) System.out.println("element " + mid +" is beyond lower and upper, add index by " + (upper-lower+1));
                    index+=upper-lower+1;
                }
            }

            if (debug) {
                System.out.println("index: " + index);
                System.out.println("midContainCount: " + midContainCount);
                System.out.println("index range: " + index + "~ " + (index + midContainCount-1));
            }




            if (targetIndex==index){
                if (debug) {
                    System.out.println("target index equals index");
                }
                if (midContainCount !=0) return mid;
                start = mid+1;
            } else if (targetIndex > index){
                if (debug) {
                    System.out.println("target index greater than index");
                }
                if (targetIndex <= (index+midContainCount-1) && midContainCount!=0) return mid;
                //else mid will have bigger value.
                start = mid +1;

            } else if (targetIndex < index){
                if (debug) {
                    System.out.println("target index less than index");
                }
                end = mid - 1;

            }
        }
        return 0;
    }

}