문제 설명

하나의 회의실이 있을 때,
서로 겹치지 않게 회의를 배정하려고 한다.

각 회의는

시작 시간, 종료 시간

이 주어지며,
다음 조건을 만족해야 한다.

한 회의가 끝나는 동시에 다음 회의 시작 가능

목표는

겹치지 않게 최대 몇 개의 회의를 배정할 수 있는가

를 구하는 것이다.

---

입력

첫째 줄

N

회의 개수

다음 줄부터

시작시간 종료시간

조건

1 ≤ N ≤ 100000

---

출력

최대 회의 개수 출력

---

입력 예시

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

출력 예시

4

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

가능한 빨리 끝나는 회의를 선택해야 한다

즉,

그리디 알고리즘

문제이다.

---

내가 작성한 코드

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Time[] time = new Time[N];
        for(int i = 0; i < N; i++) {
        	time[i] = new Time(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(time);
        int result = 0;
        int endTime = 0;
        for(Time t: time) {
        	if(t.startTime >= endTime) {
        		result++;
        		endTime = t.endTime;
        	}
        }
        System.out.println(result);
    }
}

class Time implements Comparable<Time>{
	int startTime;
	int endTime;
	
	public Time(int startTime, int endTime) {
		this.startTime = startTime;
		this.endTime = endTime;
	}

	@Override
	public int compareTo(Time o) {
		// TODO Auto-generated method stub
		if(this.endTime == o.endTime)
			return this.startTime - o.startTime;
		return  this.endTime - o.endTime;
	}
	
	
}

---

강의 코드

코드

import java.util.*;

class Meeting {
    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
    int start;
    int end;
}

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Meeting[] meetings = new Meeting[N];

        for (int i = 0; i < N; i++)
            meetings[i] = new Meeting(sc.nextInt(), sc.nextInt());

        Arrays.sort(meetings, (o1, o2) -> {
            if (o1.end == o2.end)
                return o1.start - o2.start;
            return o1.end - o2.end;
        });

        int cnt = 0, ended = 0;

        for (int i = 0; i < N; i++)
            if (ended <= meetings[i].start) {
                cnt++;
                ended = meetings[i].end;
            }

        System.out.println(cnt);
    }
}

---

내 코드 vs 강의 코드 비교

이번 문제는

완전히 동일한 코드

이다.

즉,

풀이 방식 차이 없음

---

핵심 알고리즘 (그리디)

이 문제는 대표적인 그리디 문제이다.

핵심 전략

끝나는 시간이 빠른 회의를 먼저 선택

---

왜 이게 맞는가

예를 들어

A: 1~10
B: 2~3
C: 3~4

이 있을 때

• A 선택 → 1개
• B, C 선택 → 2개

즉

짧고 빨리 끝나는 회의가 유리

---

정렬 기준이 중요한 이유

Arrays.sort(meetings, (o1, o2) -> {
    if (o1.end == o2.end)
        return o1.start - o2.start;
    return o1.end - o2.end;
});

정렬 기준

1. 종료 시간 오름차순
2. 종료 시간이 같으면 시작 시간 오름차순

---

핵심 로직

if (ended <= meetings[i].start)

의 의미

이전 회의가 끝난 이후에 시작 가능

---

시간 복잡도

• 정렬: O(N log N)
• 탐색: O(N)

전체

O(N log N)

---

핵심 개념

1. 그리디 알고리즘

매 순간 최선의 선택

---

2. 정렬 + 선택

정렬 → 순서대로 선택

---

3. 회의 문제 패턴

이 문제는 코딩테스트에서 자주 나오는

활동 선택 문제 (Activity Selection Problem)

이다.

---

정리

이 문제는 대표적인 그리디 알고리즘 문제로,
핵심은 끝나는 시간이 빠른 회의를 먼저 선택하는 것이다.

내 코드와 강의 코드는 완전히 동일하며,
중요한 것은 구현이 아니라 아이디어 자체이다.

즉,

정렬 기준을 올바르게 잡는 것이 핵심

이며, 이 기준만 이해하면 쉽게 해결할 수 있는 문제이다.