정올_1370 회의실 배정(자바) / 탐욕 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.jungol;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class jungol_1370 {
	static ArrayList<meet> meeting = new ArrayList<jungol_1370.meet>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			meeting.add(new meet(num, start, end));
		}
		Collections.sort(meeting);
		ArrayList<meet> avail = new ArrayList<meet>();
		avail.add(meeting.get(0));
		for (int i = 1; i < N; i++) {
			if(meeting.get(i).start>=avail.get(avail.size()-1).end) {
				avail.add(meeting.get(i));
			}
		}
		System.out.println(avail.size());
		for (int i = 0; i < avail.size(); i++) {
			System.out.print(avail.get(i).num+" ");
		}
	}
	
	static class meet implements Comparable<meet>{
		int num;
		int start;
		int end;
		public meet(int num, int start, int end) {
			super();
			this.num = num;
			this.start = start;
			this.end = end;
		}
		@Override
		public int compareTo(meet o) {
			// TODO Auto-generated method stub
			return this.end - o.end;
		}
		
	}
}

- 회의실 배정 문제는 최대한 많은 회의를 진행하게 만드는 문제입니다.

 

- 또한 최대한 많은 회의를 진행할 때의 회의 번호를 출력하는 문제입니다.

 

- 비교 인터페이스 Comparable를 사용해서 끝나는 시간을 정렬해줍니다.

 

- 맨 처음에 끝나는 회의를 meeting에 넣어놓고, 시작시간이 끝나는 시간 보다 늦게 하면 추가를 해줍니다.