[알고리즘] MeetingRoom 문제 [백준1931 회의실배정 java]

MeetingRoom
-Given an array of meeting time intervals consisting of start and ent times [[s1,e1],[s2,e2],...] ) (si < ei), 
determine if a person could attend all meetings.

 

Input: [[0,30], [5,10], [15,20]]

Output : flase

 

Input: [[7,10],[2,4]]

Output : true

 

문제 요약 : 회의실에는 하나의 팀만 회의가 가능하다. 회의의 시작시간과 끝나는 시간이 주어졌을 때 회의시간이 겹치지 않고 모든 회의를 끝낼 수 있다면 true를 리턴하고, 끝낼 수 없다면 false를 리턴하라.

 

풀이 

-1. 모든 회의를 끝낼 수 있는지 확인해야하기때문에 회의 시작순서로 오름차순 정렬한다.

-2. 첫번째 회의의 끝나는 시간과 다음에 이어질 회의의 시작시간을 비교해서, 전자가 더 크다면 회의를 진행할 수 없음으로 false를 리턴한다.

 

---

-code(java)

import java.util.Arrays;
import java.util.Comparator;

class Interval {
	int start;
	int end;

	Interval() {
		this.start = 0;
		this.end = 0;
	}

	Interval(int start, int end) {
		this.start = start;
		this.end = end;
	}
}

public class MeetingRoom {

	public static void main(String[] args) {

		Interval int1 = new Interval(15, 20);
		Interval int2 = new Interval(5, 10);
		Interval int3 = new Interval(0, 30);

		Interval[] intervals = { int1, int2, int3 };
		Arrays.parallelSort(intervals, comp);

		print(intervals);
		System.out.println(solve(intervals));

	}

	public static boolean solve(Interval[] intervals) {

		for (int i = 1; i < intervals.length; i++) {
			if (intervals[i - 1].end > intervals[i].start) {
				return false;
			}
		}

		return true;

	}

	public static Comparator<Interval> comp = new Comparator<Interval>() {

		@Override
		public int compare(Interval o1, Interval o2) {
			return o1.start - o2.start;
		}

	};

	public static void print(Interval[] intervals) {
		for (int i = 0; i < intervals.length; i++) {
			Interval in = intervals[i];
			System.out.println(in.start + " " + in.end);
		}
	}

}

 

---

 

관련문제 :  https://www.acmicpc.net/problem/1931

1931번: 회의실배정

MeetingRoom 문제와 유사한 그리디알고리즘 문제이다.

하나의 회의실에서 몇 팀이 회의가 가능한지 찾는 문제

풀이

-1. 회의의 시작시간과 끝 시간을 저장할 배열 class를 만든다.

-2. Comparable 을 implements 해서 정렬을 구현한다.

-3. 회의가 끝나는 시간을 기준으로 오름차순 정렬을 한다.

-4. 가장 먼저 회의를 진행하는 팀은 무조건 회의를 할 수 있기때문에 count를 1로 초기화한다.

-5. 첫번째 팀의 회의가 끝나는 시간(end)과 다음 팀의 회의 시작시간(start)를 비교한다.

==> 회의가 끝나는 시간(end)이 타 팀의 회의 시작시간(start) 보다 같거나 작다면 다음 팀이 회의가 가능하다는 뜻. 

-6. 회의가 가능한 팀마다 회의가 끝나는 시간(end)을 갱신해준다.

 

 

import java.util.Arrays;
import java.util.Scanner;

class Intervals implements Comparable<Intervals> {
	int start;
	int end;

	Intervals() {
		start = 0;
		end = 0;
	}

	Intervals(int start, int end) {
		this.start = start;
		this.end = end;
	}

	@Override
	public int compareTo(Intervals o1) {
		// TODO Auto-generated method stub
		int r = this.end - o1.end;
		if (r == 0) {
			r = this.start - o1.start;
		}
		return r;
	}

}

public class MeetingRoom_backjoon {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int testCase = sc.nextInt();

		Intervals[] in = new Intervals[testCase];

		for (int i = 0; i < testCase; i++) {
			in[i] = new Intervals(sc.nextInt(), sc.nextInt());
		}

		solve(in);

	}

	public static void solve(Intervals[] in) {
		int count = 1;
		Arrays.parallelSort(in);

		int end = in[0].end;
		for (int i = 1; i < in.length; i++) {
			if (in[i].start >= end) {
				count++;
				end = in[i].end;
			}
		}

		System.out.println(count);
	}

}

 

 

참고 : https://1-7171771.tistory.com/74?category=865872

CompareTo / Comparator