白駿1931号.
https://www.acmicpc.net/problem/1931

質問する

会議室があり、それを使用するN個の会議について、会議室使用表を作成します.各会議Iには、開始時間と終了時間があり、各会議が重複しないように、会議室の最大数を見つけます.しかし、会議が始まると、途中で中断することはできません.一つの会議が終わると同時に、次の会議が始まる可能性があります.会議の開始時間と終了時間は同じかもしれません.この場合、最初から終わっていると考えられます.

入力

1行目には、会議数N(1≦N≦100000)が与えられる.2行目からN+1行目までは各会議の情報が与えられ、これはスペースであり、会議の開始時間と終了時間を与える.開始時間および終了時間は、231−1の自然数または0以下である.

しゅつりょく

最初の行の最大使用可能な会議数を出力します.

入力例1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

サンプル出力1

4

考える

問題を解くときは難しくないが,考えれば考えるほど複雑になる.
他の人のコードと解答を参考にして解答しました.
リファレンスプール
他の人のコードや解答を見ると、完全にその通りにするよりも、
私たちは少し努力して修正し、理解する必要があると思います.
Timeclassを作成してオブジェクト型リストを作成しました

アクション

解答を見終わったら、これは難題ではないと思います.
会議室の終了時間に合わせてソートするだけです.
終了時間が同じであれば、開始時間に応じて
2つの基準を設定して並べ替えるだけで、問題を十分に解決できます.
Collectionsインタフェースのsort関数をComparatorインタフェースを使用して再定義すればよい.
それからgreedy関数から始めます.

if(prev_end_time <= time.start) {
			prev_end_time = time.end;
			count++;
  }

会議の終了時間を開始時間以上に設定します.
重ならず、最も早く会議を開始する会議を選択させます.
そして、直前の会議終了時の会議時間に応じて、会議終了時の時間をcountを増やすと、できるだけ多くの会議回数が得られます.

TMI

Greedyアルゴリズムは、他の人のコードを表示および解読するのは初めてです.
やっぱり世界には達人がたくさん...

コード#コード#

import java.io.*;
import java.util.*;
import java.util.Comparator;

public class Main {
	static List<Time> list = new ArrayList<>();
	static int N;

	static class Time {
		int start;
		int end;

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

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			list.add(new Time(start, end));
		}

		compare_sort();
	
		greedy();

	} // End of main

	static void compare_sort() {

		Collections.sort(list, new Comparator<Time>() {

			@Override
			public int compare(Main.Time o1, Main.Time o2) {

				if(o1.end == o2.end) {
					return o1.start - o2.start;
				}

				return o1.end - o2.end;
			}
		});
	}

	static void greedy() {
		int count = 0;
		int prev_end_time = 0;

		for(int i=0; i<N; i++) {
			Time time = list.get(i);

			if(prev_end_time <= time.start) {
				prev_end_time = time.end;
				count++;
			}
	

		}

		System.out.println(count);
	} // End of greedy

} // End of class