알고리즘

[Java] 백준 1931 : 회의실배정

 

문제

 

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

 

 

문제 요구조건

 

1. n개의 회의가 있다.

2. 회의 1개당 시작시간, 끝나는 시간이 있다.

3. 시작시간과 끝나는 시간이 같을 수도 있다. 

4. 회의가 중간에 중단되지는 않는다.

 

int[] conf = new int[n][2]; 로 

y축을 세로라고 생각하고 y축이 n개만큼 생성되고,

가로 축으로 2개가 생성되니 시작시간, 끝나는 시간을 담을 수 있다.

 

만들어진 2차원배열을 우선 정렬을 해야 한다.

종료시간이 작을수록 다시 시작하는 시간이 빨라질 테니까 종료시간순으로 정렬한다.

 

Arrays.sort(arr,(o1,o2)->{

//종료시간이 같다면

  if(o1[1] == o2[1]){

//시작시간 순으로

    return Integer.compare(o1[0],o2[0]);

   }else{

//같지 않으면 종료시간 순으로

    retrun Integer.compare(o1[1],o2[1]);

   }

}); 

 

* compare은 좌변이 크면 1 우변이 크면 -1 같으면 0 return

음수,0 객체의 자리가 유지, 양수인 경우 두 객체의 자리가 변경

 

이 정렬에서 시간이 많이 걸렸다.. 배울 때도 그 후에도 잘 안 써서

이번 기회에 공부를 할 수 있었다.

나머지는 간단하게 정렬된 2차원 배열을 돌면서 종료시간 변수를 만들어서

for문으로 시작시간과 비교하면서 카운트해주면 된다.

 

for(int i=0;i<n;i++) {
    	if(arryN[i][0]>=end) {
    		end=arryN[i][1];
    		cnt++;
    	}
    }

 

 

'알고리즘' 카테고리의 다른 글

10월 11일 2문제 - Java  (0) 2021.10.12
[프로그래머스] 하샤드 수  (0) 2021.05.11
[프로그래머스] 핸드폰 번호 가리기  (0) 2021.05.10
[Java] 백준 5585 : 거스름돈  (1) 2020.05.20
이진탐색  (0) 2020.05.01