백준_11000 강의실 배정 (자바) / 그리디 알고리즘

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_11000 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<lecture> arr = new ArrayList<>();
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		
		StringTokenizer st;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			arr.add(new lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		Collections.sort(arr);
		
		pq.add(arr.get(0).e);
		for (int i = 1; i < N; i++) {
			if(arr.get(i).s>=pq.peek()) {
				pq.poll();
			}
			pq.add(arr.get(i).e);
		}
		System.out.println(pq.size());
	}
	static class lecture implements Comparable<lecture>{
		int s;
		int e;
		public lecture(int s, int e) {
			super();
			this.s = s;
			this.e = e;
		}
		@Override
		public int compareTo(lecture o) {
			if(o.s==this.s) {
				return this.e-o.e;
			}
			return this.s-o.s;
		}
		
	}
}

 

※ 내 생각

이 문제는 그리디 알고리즘을 이용하는 문제입니다.
저는 강의라는 클래스를 이용해서 문제를 해결했습니다.
클래스에 대한 정렬을 하기 위해서 Comparable를 상속 받아서 정렬을 진행했습니다.
문제를 제대로 읽지 않아서 들을 수 있는 최대 강의수로 착각해서 문제를 진행했었습니다....

이 문제에서 PriorityQueue를 이용해서 문제해결을 좀 더 쉽게 했습니다.