[코드 트리] 최대로 겹치는 구간

최대로 겹치는 구간

직선 N개가 입력으로 주어지며, 선분이 겹치는 구간이 최대 몇 개인지 구하는 문제입니다.(가장 많이 겹치는 구간에서 몇 개의 선분이 겹치는가)

어떤 구간이 몇 번 겹치는 지를 배열을 통해 관리할 것입니다.

이때 겹치는 지점이냐 겹치는 구간이냐의 차이를 잘 알아두어야 합니다.

[1,5] 구간의 선분이 있고, [4,6] 구간의 선분이 있다고 가정해봅시다.

여기서는 겹치는 지점을 구하려고 한다면, 4와 5 두 지점입니다.

하지만 겹치는 구간을 구한다고 한다면 [4,5] 구간 하나입니다.

구간을 표시하는 경우에는 [x1, x2] 구간을 배열에서 x1부터 x2-1까지 표시를 해주면 됩니다. 각 구간의 시작지점에 표기하는 거랑 같은 의미입니다.

그리고 배열로 겹치는 구간을 관리하기로 했기 때문에 음수가 섞여있는 구간은 표기하기 어렵습니다. 따라서 모든 구간이 양수로 표기될 수 있도록 하는 적당한 OFFSET를 설명해주어야 합니다.

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Main {
    public static int OFFSET = 100;
    public static int lineCount;
    public static int[] overlap = new int[201];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        lineCount = Integer.parseInt(br.readLine());
        for (int i = 0; i < lineCount; i++) {
            int[] input = Arrays.stream(br.readLine().trim().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            int start = input[0]+OFFSET;
            int end = input[1]+OFFSET;
            for (int index = start; index < end; index++) {
                overlap[index]++;
            }
        }
        int answer = Arrays.stream(overlap).max().orElse(0);
        System.out.println(answer);
        br.close();
    }
}

시간복잡도

시간복잡도는 선분의 갯수(N)번 반복하고 매 반복마다 최대 구간 수(R)만큼 반복할 수 있으므로 O(NR)이 됩니다.