반응형
* 핵심
우선순위 큐를 사용해서 끝나는 순서가 빠른 순서대로 정렬
* 문제
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
* 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | import java.io.*; import java.util.*; public class Main { public static StringTokenizer stk; public static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); PriorityQueue<Info> pq = new PriorityQueue<>(); for (int i = 0; i < n; i++) { stk = new StringTokenizer(br.readLine()); pq.add(new Info(Integer.parseInt(stk.nextToken()), Integer.parseInt(stk.nextToken()))); } int end = 0; int cnt = 0; for (int i = 0; i < n; i++) { Info o = pq.poll(); if (o.start >= end) { //이전 끝난 시간보다 새로 시작하는 회의 시간이 크거나 같으면 end = o.end; cnt++; } } System.out.println(cnt); } public static class Info implements Comparable<Info> { int start, end; public Info(int start, int end) { this.start = start; this.end = end; } @Override public int compareTo(Info o) { if (end == o.end) return start - o.start; //같은 시간에 끝나면 Start 오름 차순 return end - o.end; //끝나는 순서 오름차순 정렬 } } } | cs |
반응형
'∙Algorithm' 카테고리의 다른 글
| [Algorithm] 백준/1655 :: 가운데를 말해요 (0) | 2019.04.21 |
|---|---|
| [Algorithm] 백준/1946 :: 신입 사원 (0) | 2019.03.24 |
| [Algorithm] 백준/16985 :: Maaaaaaaaaze (0) | 2019.03.01 |
| [Algorithm] 백준/11057 :: 오르막 수 (0) | 2019.02.12 |