인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

시간초과가 발생 했는데 무조건 빅오n 내에 끝내야 하는 문제 인가요??

아이디어는 가장 먼저 피로연에서 나가야하는 사람(스케쥴)을 큐(피로연)의 가장 앞에 두고 현재 도착한 사람(가장 최근 도착한 사람)의 도착 시간과 가장 먼저 나가야하는 사람의 출발 시간을 비교해서 큐에 있는 사람을 나가게 할지 남게 할지를 결정하도록 했습니다. 그런데 4번째 문제까지는 정답처리 되고 5번째 문제에서 시간 초과가 발생 하는데 혹시 n의 시간 복잡도로 풀어야 하는 문제인지 궁금해서 문의 드립니다!

import java.util.*;

public class Main {
    static public class Schedule {
        int arrive;
        int departure;

        public Schedule(int a, int d) {
            this.arrive = a;
            this.departure = d;
        }

        @Override
        public String toString() {
            return "Schedule{" +
                    "arrive=" + arrive +
                    ", departure=" + departure +
                    '}';
        }
    }

    public void solution(Schedule[] arr, int n) {
        Arrays.sort(arr, Comparator.comparing((Schedule s) -> s.arrive).thenComparing((Schedule s) -> s.departure));
        Queue<Schedule> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.departure));
        int maxCount = 0;

        for (int i = 0; i < n; i++) {
            Schedule arrived = arr[i];

            if (! pq.isEmpty()) {
                Schedule remain = pq.peek();

                if (arrived.arrive >= remain.departure) {
                    pq.poll();
                }
            }

            pq.offer(arrived);
            maxCount = Math.max(pq.size(), maxCount);
        }

        System.out.println(maxCount);
    }
/*
5
5 15
12 13
14 18
15 20
20 30
*/
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n = in.nextInt();
        Schedule[] input = new Schedule[n];
        for (int i = 0; i < n; i++) {
            input[i] = new Schedule(in.nextInt(), in.nextInt());
        }

        Main main = new Main();

//        System.out.println(main.solution(n, m));
        main.solution(input, n);
    }
}