알고리즘) 결혼식(그리디 알고리즘)

문제 ✨

 결혼식 피로연을  장소를 3일 동안 빌려 쉬지 않고 진행하려고 한다. 이에 참석하는 친구들 N명의 도착 시간과 떠날 시간을 전달받아 피로연 장소에 동시에 존재하는 최대 인원수를 구해 그 인원을 수용할 수 있는 장소를 빌리려 한다. 만약 도착 시간 13시이고 떠날 시간 15시라면, 이 친구는 13시에는 피로연 장소에 존재하나 15시에는 존재하지 않는다고 가정한다. 피로연장에 동시에 존재하는 최대 인원을 출력해야 한다. 피로연은 0시부터 72시까지 진행한다.)

풀이 ✨

 시간의 범위를 0부터 72까지 변화시키며(아래 코드에서는 정렬된 배열의 첫 번째 요소 - 친구 - 의 도착 시간을 출발값으로 정의) 당시의 시간과 출발 시간이 겹치는 친구가 있을 때에는 동시에 존재하는 인원(cnt)를 증가시키고, 당시 시간과 떠나는 시간이 겹치는 친구가 있을 때에는 동시에 존재하는 인원(cnt)를 감소시킨다.

작성 코드 ✍️

import java.util.*;

public class Main {
	static int n;
	static Item[] list;
	static int max = Integer.MIN_VALUE;
	
	static class Item implements Comparable<Item> {
		int start;
		int end;
		
		public Item(int start, int end) {
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Item o) {
			return o.start - this.start;
		}
	}
	
	static void solution() {
		int cnt = 0; // 누가 오고 갈 때마다 카운트를 조정하는 것이 포인트 💫
		for (int k = list[0].start; k < 72; k++) {
			for (int i = 0; i < n; i++) {
				if (list[i].start == k) cnt++;
				else if (list[i].end == k) cnt--;
				
				max = Math.max(max, cnt);
			}
		}
		
	}

	public static void main(String[] args) {
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		list = new Item[n];
		for (int i = 0; i < n; i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			list[i] = new Item(start, end);
		}
		Arrays.sort(list);
		System.out.println(max);
	}
}