[백준] 9576 책 나눠주기 / 자바(Java)

문제

https://www.acmicpc.net/problem/9576

9576번: 책 나눠주기

 

---

해설

그리디 알고리즘을 사용해 가장 많은 책을 주는 방법을 찾습니다.

책의 범위에서 시작의 오름차순으로 정렬해 그 중 가장 앞에 있는 것부터 하나씩 준다고 생각합니다.

 

책은 1~N까지로 정해져있기 때문에 selected배열을 통해 준 책과 안준 책을 분류합니다.

이후 책 범위를 정렬해 각자 최저번호에 가까운 책을 줍니다. 

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static class set implements Comparable<set>{
		int start,end;

		public set(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(set o) {
			// TODO Auto-generated method stub
			return this.end!=o.end ? this.end-o.end : this.start-o.start;
		}

		@Override
		public String toString() {
			return "set [start=" + start + ", end=" + end + "]";
		}
		
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st ;
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1;tc<=T;tc++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			boolean[] selected = new boolean[N+1];
			set choose[] = new set[M+1];
			choose[0] = new set(0,0);
			for(int i=1;i<=M;i++) {
				st = new StringTokenizer(br.readLine());
				choose[i] = new set(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

			}
			Arrays.sort(choose);
			
			int ans = 0;
			for(int i=1;i<=M;i++) {
				int start = choose[i].start;
				int end = choose[i].end;
				for(int j=start;j<=end;j++) {
					if(!selected[j]) {
						selected[j] = true;
						ans++;
						break;
					}
				}
			}

			System.out.println(ans);
		}
	}
}