There is one meeting room and n meetings you would like to hold. Meeting i starts at time sᵢ and ends at eᵢ (sᵢ < eᵢ). The room holds only one meeting at a time, and a meeting cannot be paused once it starts. A meeting may start at the very moment another one ends (e.g. 1–3 and 3–5 can both be held). Print the largest number of meetings that can be held without overlapping.
The first line gives n, then n lines give sᵢ and eᵢ separated by a space. The same meeting may appear more than once.
Input
1 ≤ n ≤ 5,000, 0 ≤ sᵢ < eᵢ ≤ 10⁹
Output
The largest number of meetings that can be held (one integer)
Example 1 · stdin
5
1 4
3 5
0 6
5 7
8 9
stdout
3
Example 2 · stdin
3
1 3
3 5
2 4
stdout
2
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Look at meetings in order of earliest end time and take every one that starts after the room is free: that gives the most (ending earlier always leaves at least as much time afterwards). Four traps: choosing by earliest start lets one long meeting block many short ones. Choosing the shortest first also fails: a short meeting straddling two others blocks both. start > freeAt throws away meetings that touch and is wrong; start >= freeAt is right. And how you give a sort key differs by language: Python sort(key=lambda m: m[1]), Java Arrays.sort(a, Comparator.comparingInt(m -> m[1])), C# LINQ OrderBy(m => m.End) (tuples can have named fields), C++ std::sort with a lambda returning a.second < b.second, C qsort with a compare function returning negative/0/positive (a - b can overflow for large ranges, so (a > b) - (a < b) is safer). JavaScript and TypeScript must pass a compare function (a, b) => a[1] - b[1] — a bare sort() compares as strings, putting "100,5" before "20,1". Craykon defines endFirst(a, b) { return a[1] - b[1]; } and passes it as meetings.Sort(endFirst). It is n log n, so n = 5,000 is instant.
Pythonmain.py · 15 lines
import sysdata = 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)
JavaScriptmain.js · 16 lines
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);
TypeScriptmain.ts · 17 lines
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);
JavaMain.java · 31 lines
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); }}
C#Main.cs · 27 lines
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); }}
C++main.cpp · 25 lines
#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';}
Cmain.c · 33 lines
#include <stdio.h>#include <stdlib.h>#define MAXN 5000typedef 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;}
Craykonmain.cray · 26 lines
// 끝나는 시각이 이른 것이 앞에 오게 하는 비교 함수끝먼저(앞, 뒤){ return 앞[1] - 뒤[1];}n = Console.ReadLine().ToNumber();meetings = [];for (i = 0; i < n; i++){ meetings.Add(Console.ReadNumbers()); // [시작, 끝]}// 일찍 끝나는 회의부터 본다: 일찍 끝날수록 뒤에 남는 시간이 많다meetings.Sort(끝먼저);count = 0;freeAt = 0; // 회의실이 비는 시각foreach (m in meetings){ if (m[0] >= freeAt) { count += 1; freeAt = m[1]; }}Console.WriteLine(count);