[Algorithm]알고리즘 자바_69 결혼식

💬 문제 설명

현수는 다음 달에 결혼을 합니다. 현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.

피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다. 각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.

현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.

만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.

 

🔨 입출력 예

- 입력 

• 첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.
• 두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.
• 시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다.

5
14 18
12 15
15 20
20 30
5 14

 

- 출력

• 첫째 줄에 피로연장에 동시에 존재하는 최대 인원을 출력하세요.

 

2

 

 

💻 Solution.java

1. 들어오는 시간과 나가는 시간을 나눠 모두 기록한다.
2. 들어오는 시간에는 인원수를 증가시키고, 나가는 시간에는 인원수를 감소 시킨다.

/* 회의실 배정 :: 그리디 알고리 */

import java.util.*;
class Time implements Comparable<Time>{
	public int s, e;
	Time(int s, int e){
		this.s = s;
		this.e = e;
	}
	
	@Override
	public int compareTo(Time o) { //object가 더 크면 음수 리턴, this가 더 크면 양수 리턴, 같은 값은 0 리턴
		if(this.e == o.e) return this.s - o.s;
		else return this.e - o.e;
	}
}

public class Main {
	
	public int solution(ArrayList<Time> arr, int n) {
		int cnt = 0;
		
		Collections.sort(arr);
		int et = 0;
		for(Time ob : arr) {
			if(ob.s >= et) {
				cnt++;
				et=ob.e;
			}
		}
		return cnt;
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		ArrayList<Time> arr = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			arr.add(new Time(x, y));
		}
		
		System.out.println(main.solution(arr, n));
		
		sc.close();
		return ;
	}
}