회의실이 하나 있고, 열고 싶은 회의 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()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
끝나는 시각이 이른 회의부터 보면서, 회의실이 빈 뒤에 시작하는 회의를 모두 고르면 가장 많아요(일찍 끝낼수록 뒤에 남는 시간이 많아서 손해가 없어요).
함정 넷: 일찍 시작하는 것부터 고르면 긴 회의 하나가 짧은 회의 여럿을 막아요.
짧은 것부터 골라도 두 회의 사이에 걸친 짧은 회의가 둘을 막아요.
맞닿는 회의를 버리는 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"보다 앞에 와요.
크레이콘은 끝먼저(앞, 뒤) { 돌려주기 앞[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);