

종료시간이 빠른 순으로 정렬해서 푸는
기본적인 그리디문제처럼 보이지만 주의해야 할 점이 있다.
그저 종료시간이 빠른 순으로 정렬하기만 해서는
3
3 3
3 3
1 3
이 입력으로 주어졌을 때
올바른 출력값은 3인데 2가 출력되는 문제가 발생한다.
종료시간은 같은데 시작시간은 더 빠른 회의가 제대로 처리되지 않는 것이다.
이 문제를 해결하는 방법은 간단하다.
종료시간이 빠른 순으로 정렬하되,
종료시간이 같을 때는 시작시간이 빠른 순으로 정렬을 하는 것이다.
이렇게 정렬한 뒤에는 한 회의의 시작시간 >= 현재 진행된 시간이면 회의를 하도록
코드를 짜주면 된다.
import java.io.*; import java.util.*; public class Main { static class Meeting{ int start; int end; Meeting(int start, int end){ this.start = start; this.end = end; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); ArrayList<Meeting> list = new ArrayList<>(); for(int i=0;i<N;i++) { StringTokenizer st = new StringTokenizer(br.readLine()," "); list.add(new Meeting(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()))); } list.sort((o1, o2)->{ if(o1.end==o2.end) { return o1.start-o2.start; } return o1.end-o2.end; }); int cnt = 0; int time = -1; for(int i=0;i<list.size();i++) { Meeting m = list.get(i); if(time<=m.start) { time = m.end; cnt++; } } System.out.println(cnt); } }
'Algorithm > [BOJ] - JAVA' 카테고리의 다른 글
[백준] 10789 : 세로읽기 Java (0) | 2024.01.17 |
---|---|
[백준] 10815 : 숫자 카드 JAVA 풀이 (0) | 2022.12.02 |
[백준] 2783 : 삼각 김밥 JAVA 풀이 (0) | 2022.11.02 |
[백준] 1783 : 병든 나이트 JAVA 풀이 (0) | 2022.10.30 |
[백준] 2875 : 대회 or 인턴 JAVA 풀이 (0) | 2022.10.30 |