[ 백준 ] 1931번 : 회의실 배정 - ( C++/C , JAVA/자바, PYTHON/파이썬 )

• 문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

• 풀이법 ( 알고리즘 )

https://kim6394.tistory.com/67 글을 참조하였다.

 

시작 시간이 빨라도 종료 시간이 늦게 끝나면 최대 회의 수를 가질 수 없다.

따라서 vector 컨테이너에 회의의 시작 시간과 종료 시간을 저장한 후 정렬을 한다.

 

이때 끝나는 시간이 같다면 시작하는 시간이 빠른 순으로 정렬하고, 끝나는 시간이 같지 않다면 종료 시간이 빠른 순으로 정렬한다.

 

그리디는 최선의 선택을 한다는 점이 어렵게 다가오는 거 같다.

---

• 풀이 - C++ ( C )

#include <iostream>
#include <algorithm> // sort
#include <vector> 

using namespace std;

int n; // n : 회의의 수

struct Time {
	int start;
	int end;
};

bool compare(Time x, Time y) {
	if (x.end == y.end) // 끝나는 시간이 같다면
		return x.start < y.start; //시작하는 시간이 빠른 순으로 정렬 
	else return x.end < y.end; // 종료시간이 빠른 순으로 정렬
}

int main(void)
{
	//input
	cin >> n;

	//solve
	vector <Time> schedule(n);
	for (int i = 0; i < n; i++)
		cin >> schedule[i].start >> schedule[i].end;

	sort(schedule.begin(), schedule.end(), compare); //정렬

	int cnt = 0; // 회의 가능한 수
	int ending_time = 0; // 회의의 종료 지점

	for (int i = 0; i < schedule.size(); i++)
	{
		if (ending_time <= schedule[i].start) // 회의의 종료 시점이 다음 회의의 시작지점보다 빠르면
		{
			ending_time = schedule[i].end; // ending_time에 다음 회의의 종료 시점 저장
			cnt++;
		}
	}

	//output
	cout << cnt;
	return 0;
}

• 풀이 - JAVA

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[][] schedule = new int[n][2]; // schedule[][0] : 시작지점 , schedule[][1] : 종료지점
		
		for(int i = 0; i < n; i++) {
			schedule[i][0] = sc.nextInt();
			schedule[i][1] = sc.nextInt();
		}
		
		Arrays.sort(schedule, new Comparator<int[]>() {
			
			@Override 
			public int compare(int[] x, int[] y) {
				
				//끝나는 시간이 같은 경우
				if(x[1] == y[1]) return x[0] - y[0]; // 시작 시간이 빠른 순 정렬
				else return x[1] - y[1];
			}
		});
	
		int cnt = 0;
		int ending_time = 0;
		
		for(int i = 0; i < n; i++)
		{
			//전 회의의 종료시간이 다음 회의의 시작시간보다 작거나 빠르다면 갱신
			if(ending_time <= schedule[i][0])
			{
				ending_time = schedule[i][1];
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}

}

• 풀이 - PYTHON

n = int(input())

schedule = []

for _ in range(n):
    start, end = map(int,input().split())
    schedule.append((start,end))

schedule = sorted(schedule, key = lambda a:a[0])
schedule = sorted(schedule, key = lambda a:a[1])

cnt = 0
before_end = 0

for start,end in schedule:

    if start >= before_end:
        cnt += 1
        before_end = end

print(cnt)