구간의 합집합

구간의 합집합 (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.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static long finalResult = 0;

    //    public static long max = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        long b[][];
        long c;
        int d[];
        int count = 0;
        long max = Integer.MIN_VALUE;
        a = sc.nextInt();

        b = new long[a][2];

        for (int i = 0; i < a; i++) {
            b[i][0] = sc.nextLong();
            b[i][1] = sc.nextLong();
            if (max < b[i][1]) max = b[i][1];
        }

        c = sc.nextLong();

        countN(0, Long.MAX_VALUE, b, c);

        System.out.println(finalResult);

        sc.close();

    }

    public static int findN(long[][] b, long k, long target, boolean x) {
        long result = 0;

        for (int i = 0; i < b.length; i++) {
            long left = b[i][0];
            long right = b[i][1];

            if (right < k) result += right - left + 1;
            else if (right >= k && left <= k) result += k - left;
        }

        if (x && result == target && findN(b, k + 1, target, false) == 0 && findN(b, k - 1, target, false) == -1)
            return 1;
        else if (result > target) return 0;
        else if (x && result < target && findN(b, k + 1, target, false) == 0) return 1;
        else return -1;

    }


    public static void countN(long s, long e, long[][] b, long target) {
        if (s > e) return;
        else {
            long mid = (s + e) / 2;
            int result = findN(b, mid, target, true);

            if (result == 1) finalResult = mid;
            else if (result == 0) countN(s, mid - 1, b, target);
            else {
                countN(mid + 1, e, b, target);
            }
        }

    }

}