1931문제 회의실 배정(그리디) Java

1931문제 회의실 배정(그리디) Java

728x90

반응형

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

출처:

##문제이해##

0시부터 24시까지 존재한다고 가정했을때

각각 0~24까지 가장 적은시간을 필요로하는 걸 찾아서 안겹치는걸 비교해서 가져온다.

안겹치는부분을 어떻게 해야하는지를 고민하다..결국 직접비교를 수행했다.

##기타사항##

시작시간과 끝시간을 비교하는것과 원하는 방식으로 정렬시키는게 포인트 인것 같다.(ex 1~4 -->5~7)

예제로 주어진 코드의 경우 sort을 하든 안하든 동일한 값을 가지고있어서 처음에는 sort을 안한상태로 진행했었는데.. 틀렸다고 떠서 참고했다

##참고한 블로그##

https://st-lab.tistory.com/145

##내 코드##

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class boj_1931 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); /* time[][0] 은 시작시점을 의미 time[][1] 은 종료시점을 의미 */ int[][] time = new int[N][2]; for(int i = 0; i < N; i++) { time[i][0] = in.nextInt(); // 시작시간 time[i][1] = in.nextInt(); // 종료시간 } //종료시간 기준으로 정렬 Arrays.sort(time,new Comparator() { //비교부분 @Override public int compare(int[] o1, int[] o2) { //종료시간이 만약 같은경우에는 시작시간 순서로 정렬 if(o1[1]==o2[1]) { return o1[0]-o2[0]; } return o1[1]-o2[1]; //종료시간 기준으로 정렬 } }); //뒤에서부터 종료시간과 시작시간이 짧은걸 체크하기 시작한다. int cnt =0; int end= 0;//시간 초기셋팅 for(int i=0; i

728x90

반응형

from http://lollaziest.tistory.com/156 by ccl(A) rewrite - 2021-09-24 18:01:14