[SWEA] 5202. 화물도크

       문제 요약        

- 문제

작업 시작시간, 완료시간 주어짐할 수 있는 최대 작업의 수 구하기

 

         아이디어        

 

끝나는 시각이 빠른 순으로 정렬

같은 시간 내에 가장 많은 작업을 하려면 끝나는 시각이 빨라야한다 

 

         소스코드        

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

public class Solution {
	static int T;
	static int N;// 신청서
	// 작업 시작 시간 s - 작업 종료 시간 e
	static List<Item> items;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for (int test = 1; test <= T; test++) {
			items = new ArrayList<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				items.add(new Item(s, e));
			}
			Collections.sort(items);
			int cnt = 0;
			int lastTime = 0;
			for (int i = 0; i < items.size(); i++) {
				Item item = items.get(i);
				if (lastTime <= item.s) {
					cnt += 1;
					lastTime = item.e;
				}
			}
			System.out.println("#" + test + " " + cnt);

		}
	}

	static class Item implements Comparable<Item> {
		int s, e;

		Item(int s, int e) {
			this.s = s;
			this.e = e;
		}

		@Override
		public int compareTo(Item o) {
			if (this.e == o.e) {
				return o.s - this.s;
			}
			return -o.e + this.e;
		}

		@Override
		public String toString() {
			return "" + this.s + " - " + this.e;
		}
	}

}