[코드트리] 최대로 겹치는 지점

최대로 겹치는 지점

1차원 직선 상의 여러 개의 선분이 존재하는데 이 선분이 겹치는 지점의 최대값을 구하는 문제입니다.

각 선분들의 1차원 직선 상에서 지점을 지나는 것을 기준으로 삼기 때문에 [2,5] 길이의 지점은 2, 3, 4, 5 지점을 지난다고 생각해야합니다.

그리고 겹치는 지점은 1차원 배열로 관리합니다.

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

public class Main {
    public static int lineCount;
    public static int[] overlap = new int[101];
    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().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = input[0], end = input[1];
            for (int index = start; index <= end; index++) {
                overlap[index]++;
            }
        }
        System.out.println(Arrays.stream(overlap).max().getAsInt());
        br.close();
    }
}

시간복잡도

선분의 갯수(N)만큼 반복하고 매 반복마다 최대 선분의 길이(R)만큼 반복하므로 O(NR)이라고 할 수 있습니다.