会議室が一つあり、開きたい会議が n 個ある。
i 番の会議は時刻 sᵢ に始まり eᵢ に終わる（sᵢ < eᵢ）。
会議室では一度に一つの会議しか開けず、会議は始まったら途中で止まらない。
ある会議が終わるちょうどその時刻に次の会議を始めてもよい（例：1〜3 と 3〜5 はどちらも開ける）。
重ならずに開ける会議の最大の個数を出力せよ。
一行目に n、続く n 行に sᵢ と eᵢ が空白区切りで与えられる。
まったく同じ会議が複数回現れることもある。
5 1 4 3 5 0 6 5 7 8 9
3
3 1 3 3 5 2 4
2
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
終わる時刻が早い会議から見ていき、会議室が空いたあとに始まる会議をすべて選ぶと最大になります（早く終わるほど後に残る時間が多いので損がありません）。
罠は四つ：早く始まるものから選ぶと、長い会議一つが短い会議いくつもをふさぎます。
短いものから選んでも、二つの会議にまたがる短い会議が二つをふさぎます。
接する会議を捨てる start > freeAt は誤りで、start >= freeAt が正解です。
そして並べ替えの基準の渡し方は言語ごとに違います：Python sort(key=lambda m: m[1])、Java Arrays.sort(a, Comparator.comparingInt(m -> m[1]))、C# LINQ OrderBy(m => m.End)（タプルに名前を付けられます）、C++ std::sort に a.second < b.second を返すラムダ、C qsort に負・0・正を返す比較関数（a - b は範囲が大きいとあふれることがあるので (a > b) - (a < b) が安全）。
JavaScript・TypeScript は比較関数 (a, b) => a[1] - b[1] を必ず渡します — なしで sort() すると文字列として比べて "100,5" が "20,1" より前に来ます。
Craykon は 終わり先(前, 後) { 返す 前[1] - 後[1]; } を作って meetings.並べ替え(終わり先) に渡します。
n log n なので n = 5,000 も一瞬です。
import sys data = sys.stdin.read().split()n = int(data[0])meetings = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)] # 일찍 끝나는 회의부터 본다: 일찍 끝날수록 뒤에 남는 시간이 많다meetings.sort(key=lambda m: m[1])count = 0free_at = 0 # 회의실이 비는 시각for start, end in meetings: if start >= free_at: # 앞 회의가 끝나는 바로 그 시각에 시작해도 된다 count += 1 free_at = endprint(count)const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = t[0];const meetings = [];for (let i = 0; i < n; i++) meetings.push([t[1 + 2 * i], t[2 + 2 * i]]); // 일찍 끝나는 회의부터 본다. 비교 함수가 없으면 sort()는 글자로 비교한다meetings.sort((a, b) => a[1] - b[1]);let count = 0;let freeAt = 0; // 회의실이 비는 시각for (const [start, end] of meetings) { if (start >= freeAt) { // 앞 회의가 끝나는 바로 그 시각에 시작해도 된다 count++; freeAt = end; }}console.log(count);import { readFileSync } from "node:fs";const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = t[0];const meetings: [number, number][] = [];for (let i = 0; i < n; i++) meetings.push([t[1 + 2 * i], t[2 + 2 * i]]); // 일찍 끝나는 회의부터 본다. 비교 함수가 없으면 sort()는 글자로 비교한다meetings.sort((a, b) => a[1] - b[1]);let count = 0;let freeAt = 0; // 회의실이 비는 시각for (const [start, end] of meetings) { if (start >= freeAt) { // 앞 회의가 끝나는 바로 그 시각에 시작해도 된다 count++; freeAt = end; }}console.log(count);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Comparator;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); int[][] meetings = new int[n][2]; for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); meetings[i][0] = Integer.parseInt(st.nextToken()); meetings[i][1] = Integer.parseInt(st.nextToken()); } // 일찍 끝나는 회의부터 본다: 일찍 끝날수록 뒤에 남는 시간이 많다 Arrays.sort(meetings, Comparator.comparingInt(m -> m[1])); int count = 0; int freeAt = 0; // 회의실이 비는 시각 for (int[] m : meetings) { if (m[0] >= freeAt) { // 앞 회의가 끝나는 바로 그 시각에 시작해도 된다 count++; freeAt = m[1]; } } System.out.println(count); }}using System;using System.Linq; class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]); var meetings = Enumerable.Range(0, n) .Select(i => (Start: int.Parse(t[1 + 2 * i]), End: int.Parse(t[2 + 2 * i]))) .OrderBy(m => m.End) // 일찍 끝나는 회의부터 본다 .ToList(); int count = 0; int freeAt = 0; // 회의실이 비는 시각 foreach (var m in meetings) { if (m.Start >= freeAt) // 앞 회의가 끝나는 바로 그 시각에 시작해도 된다 { count++; freeAt = m.End; } } Console.WriteLine(count); }}#include <algorithm>#include <iostream>#include <utility>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<std::pair<int, int>> meetings(n); // (시작, 끝) for (auto& [start, end] : meetings) std::cin >> start >> end; // 일찍 끝나는 회의부터 본다: 일찍 끝날수록 뒤에 남는 시간이 많다 std::sort(meetings.begin(), meetings.end(), [](const auto& a, const auto& b) { return a.second < b.second; }); int count = 0; int freeAt = 0; // 회의실이 비는 시각 for (const auto& [start, end] : meetings) { if (start >= freeAt) { // 앞 회의가 끝나는 바로 그 시각에 시작해도 된다 count++; freeAt = end; } } std::cout << count << '\n';}#include <stdio.h>#include <stdlib.h> #define MAXN 5000 typedef struct { int start, end;} Meeting; /* 끝나는 시각이 이른 것이 앞. 빼기(a - b) 대신 비교해서 넘침 걱정을 없앤다 */static int by_end(const void *x, const void *y) { const Meeting *a = x, *b = y; return (a->end > b->end) - (a->end < b->end);} int main(void) { static Meeting meetings[MAXN]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d %d", &meetings[i].start, &meetings[i].end); qsort(meetings, n, sizeof(Meeting), by_end); int count = 0; int free_at = 0; /* 회의실이 비는 시각 */ for (int i = 0; i < n; i++) { if (meetings[i].start >= free_at) { /* 끝나는 바로 그 시각에 시작해도 된다 */ count++; free_at = meetings[i].end; } } printf("%d\n", count); return 0;}// 끝나는 시각이 이른 것이 앞에 오게 하는 비교 함수끝먼저(앞, 뒤){ 返す 앞[1] - 뒤[1];} n = コンソール.行読み().数に();meetings = [];繰り返す (i = 0; i < n; i++){ meetings.追加(コンソール.数読み()); // [시작, 끝]} // 일찍 끝나는 회의부터 본다: 일찍 끝날수록 뒤에 남는 시간이 많다meetings.並べ替え(끝먼저);count = 0;freeAt = 0; // 회의실이 비는 시각それぞれ (m の中 meetings){ もし (m[0] >= freeAt) { count += 1; freeAt = m[1]; }}コンソール.書く(count);