회의실 배정

설명

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다.

각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

 

입력

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데

이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.

회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

예시 입력 1

5
1 4
2 3
3 5
4 6
5 7

예시 출력 1

3

예시 입력 2

3
3 3
1 3
2 3

예시 출력 2

2

 

내가 작성한 문제 이해

 

선생님 문제 이해

다른 건 나와 같고,

💡 나는 : 인덱스i의 끝시간 ≤ 인덱스i+1의 첫시간이라면, cnt++
—> 문제점 인덱스를 어떻게 뽑을 것인가 이슈 존재

선생님: 비교값으로 쓰일 tmp 선언 후 0으로 초기화,
t.f ≥ tmp 면 cnt++ 그리고 tmp를 t.l로 변경

 

case1. tmp 변경을 첫시간으로 하는 경우

import java.util.*;

class Time implements Comparable<Time> {
	int f,l;
	
	// 매개변수가 있는 생성자
	Time(int f, int l) {
		this.f = f;
		this.l = l;
	}
	
	// 오버라이드, compareTo를 통한 정렬
	@Override 
	public int compareTo(Time t) {
		// 끝시간이 같을 때, 첫시간 오름차순 정렬 this- t
		if(this.l == t.l) {
			return this.f - t.f;
		}else {
			// 끝시간 오름차순 this- t
			return this.l - t.l;
		}
	}
}

public class Conference {
	public int solution(ArrayList<Time> arr) {
		int cnt =0;
		// 임시값 0 초기화
		int tmp = 0;
		for(Time t : arr) {
			if(t.f >= tmp) {
				cnt++;
				// 제일 중요 : tmp = t.f과 결과 비교
				tmp = t.f;
			}
		}
		return cnt;
	}

	public static void main(String[] args) {
		Conference T = new Conference();
		// 입력 두 번 받음 : 총n, ArrayList로 n만큼
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		// ArrayList 선언
		ArrayList<Time> arr = new ArrayList<>();
		// for문 돌면서 입력받음
		for(int i=0; i<n; i++) {
			int f = kb.nextInt();
			int l = kb.nextInt();
			arr.add(new Time(f,l));
		}
		// 정렬 : 끝시간으로 정렬되어짐
		Collections.sort(arr);
		// 넘겨줌
		System.out.println(T.solution(arr));
		
	}

}

 

tmp = t.f; 으로 했을 때 에러 발생 케이스 분석

i)

입력값

5
1 4
2 3
3 5
4 6
5 7

리턴값

4

정닶값

3

 

ii)

입력값

5
3 3
1 3
2 3
4 6
5 7

리턴값

5

정답값

3

 

 

case2. tmp 변경을 끝시간으로 하는 경우(정답)

import java.util.*;

class Time implements Comparable<Time> {
	int f,l;
	
	// 매개변수가 있는 생성자
	Time(int f, int l) {
		this.f = f;
		this.l = l;
	}
	
	// 오버라이드, compareTo를 통한 정렬
	@Override 
	public int compareTo(Time t) {
		// 끝시간이 같을 때, 첫시간 오름차순 정렬 this- t
		if(this.l == t.l) {
			return this.f - t.f;
		}else {
			// 끝시간 오름차순 this- t
			return this.l - t.l;
		}
	}
}

public class Conference {
	public int solution(ArrayList<Time> arr) {
		int cnt =0;
		// 임시값 0 초기화
		int tmp = 0;
		for(Time t : arr) {
			if(t.f >= tmp) {
				cnt++;
				// 제일 중요 : tmp = t.f과 결과 비교
				tmp = t.l;
			}
		}
		return cnt;
	}

	public static void main(String[] args) {
		Conference T = new Conference();
		// 입력 두 번 받음 : 총n, ArrayList로 n만큼
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		// ArrayList 선언
		ArrayList<Time> arr = new ArrayList<>();
		// for문 돌면서 입력받음
		for(int i=0; i<n; i++) {
			int f = kb.nextInt();
			int l = kb.nextInt();
			arr.add(new Time(f,l));
		}
		// 정렬 : 끝시간으로 정렬되어짐
		Collections.sort(arr);
		// 넘겨줌
		System.out.println(T.solution(arr));
		
	}

}

 

 

💡적절히 tmp만들어서 최솟값, 최댓값, 0으로 초기화하고 비교값으로 사용하는 게 중요!