회의실 하나의 하루 예약 n건과 질문 q개가 주어진다.
시각은 0 이상의 정수다.
첫 줄에 n과 q가 주어진다.
다음 n줄에 예약이 한 줄에 하나씩 "s e" 꼴로 주어진다. 이 예약은 시각 s부터 e 직전까지 회의실을 쓴다. 그래서 시각 s에는 쓰는 중이고 시각 e에는 이 예약으로 쓰는 중이 아니다.
예약은 시작 시각이 빠른 차례로 주어지고, 서로 겹치지 않는다.
하지만 앞 예약이 끝나는 시각에 다음 예약이 바로 시작할 수는 있다. 이런 예약들은 맞닿아 있다고 한다.
마지막 줄에 질문할 시각 t가 q개 빈칸으로 띄워 주어진다.
질문마다 한 줄에 답을 출력하라.
시각 t에 회의실을 쓰는 예약이 있으면 "busy X"를 출력한다. X는 그 예약과, 그 뒤로 맞닿아 이어지는 예약들이 모두 끝나 회의실이 처음 비는 시각이다.
시각 t에 쓰는 예약이 없으면 "free Y"를 출력한다. Y는 t보다 뒤에 시작하는 예약 가운데 가장 빠른 것의 시작 시각이다.
t보다 뒤에 시작하는 예약이 없으면 "free none"을 출력한다.
예약과 질문이 많으니, 질문마다 예약을 처음부터 훑지 말고 반으로 나눠 찾아라.
입력
1 ≤ n ≤ 10,000, 1 ≤ q ≤ 10,000, 0 ≤ s < e ≤ 1,000,000,000, 앞 예약의 e ≤ 다음 예약의 s, 0 ≤ t ≤ 1,000,000,000
출력
질문마다 한 줄: busy X, free Y, free none 가운데 하나
예시 1 · stdin
3 6
9 10
10 12
14 16
9 11 12 13 16 3
stdout
busy 12
busy 12
free 14
free 14
free none
free 9
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
정렬된 배열에서 찾는 도구가 언어마다 달라요. Python bisect.bisect_right(S, t), C++ std::upper_bound는 t보다 큰 첫 자리를 주니 그 바로 앞이 "시작 시각이 t 이하인 마지막 예약"이에요. Java Arrays.binarySearch, C# Array.BinarySearch는 같은 값을 찾으면 그 자리를, 못 찾으면 음수 -(넣을 자리) - 1을 돌려줘요(C#은 ~pos로 넣을 자리를 꺼내요). 같은 값이 여럿이면 어느 자리를 줄지 약속하지 않지만, 이 문제는 시작 시각이 모두 달라서 쓸 수 있어요. JS·TS·크레이콘에는 이런 함수가 없고, C의 bsearch는 같은 값만 찾아 주니 직접 써요. lo, hi를 "S[0..lo)는 t 이하, S[hi..n)은 t 초과"로 두고 줄이면 끝날 때 lo - 1이 답이에요. 크레이콘과 JS의 /는 소수까지 나누니 가운데는 수학.몫(lo + hi, 2)나 >> 1로 구해요. 첫째 함정은 경계예요. bisect_left(같은 값의 앞 자리)를 쓰면 t가 예약의 시작 시각과 같을 때 그 예약을 못 봐요. 예약은 e 직전까지라 t == e이면 그 예약으로는 쓰는 중이 아니니 t < E[i]예요. 둘째 함정은 첫 예약보다 이른 t예요. 찾은 번호가 -1인데, Python은 E[-1]이 오류가 아니라 마지막 예약이라서 엉뚱하게 busy가 나와요. Java·C#·크레이콘은 범위 밖 읽기 오류로 멈추고, JS·TS는 undefined가 나와 비교가 늘 거짓이 되고, C·C++은 정의되지 않은 동작이라서 먼저 i >= 0을 물어요. 셋째로, 맞닿은 예약을 질문마다 따라가면 사슬이 길 때 느리니, 뒤에서부터 "여기서 이어지다 처음 비는 시각"을 한 번 채워 두어요.
Pythonmain.py · 25 줄
import sysfrom bisect import bisect_rightdata = sys.stdin.read().split()n, q = int(data[0]), int(data[1])S = [int(x) for x in data[2:2 + 2 * n:2]]E = [int(x) for x in data[3:3 + 2 * n:2]]queries = data[2 + 2 * n:]# block_end[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)block_end = E[:]for i in range(n - 2, -1, -1): if E[i] == S[i + 1]: block_end[i] = block_end[i + 1]out = []for t in map(int, queries): i = bisect_right(S, t) - 1 # 시작 시각이 t 이하인 마지막 예약(없으면 -1) if i >= 0 and t < E[i]: # i가 -1이면 E[-1]이 마지막 예약이 되니 먼저 확인한다 out.append(f"busy {block_end[i]}") elif i + 1 < n: out.append(f"free {S[i + 1]}") else: out.append("free none")print("\n".join(out))
JavaScriptmain.js · 31 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = data;const S = [], E = [];for (let i = 0; i < n; i++) { S.push(data[2 + 2 * i]); E.push(data[3 + 2 * i]);}// blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)const blockEnd = E.slice();for (let i = n - 2; i >= 0; i--) if (E[i] === S[i + 1]) blockEnd[i] = blockEnd[i + 1];// 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1)function lastStartAtMost(t) { let lo = 0, hi = n; // 답은 [lo, hi) 바로 앞: S[0..lo)는 t 이하, S[hi..n)은 t 초과 while (lo < hi) { const mid = (lo + hi) >> 1; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1;}const out = [];for (let j = 0; j < q; j++) { const t = data[2 + 2 * n + j]; const i = lastStartAtMost(t); if (i >= 0 && t < E[i]) out.push(`busy ${blockEnd[i]}`); else if (i + 1 < n) out.push(`free ${S[i + 1]}`); else out.push("free none");}console.log(out.join("\n"));
TypeScriptmain.ts · 32 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, q] = data;const S: number[] = [], E: number[] = [];for (let i = 0; i < n; i++) { S.push(data[2 + 2 * i]); E.push(data[3 + 2 * i]);}// blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)const blockEnd: number[] = E.slice();for (let i = n - 2; i >= 0; i--) if (E[i] === S[i + 1]) blockEnd[i] = blockEnd[i + 1];// 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1)function lastStartAtMost(t: number): number { let lo = 0, hi = n; // S[0..lo)는 t 이하, S[hi..n)은 t 초과 while (lo < hi) { const mid: number = (lo + hi) >> 1; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1;}const out: string[] = [];for (let j = 0; j < q; j++) { const t: number = data[2 + 2 * n + j]; const i: number = lastStartAtMost(t); if (i >= 0 && t < E[i]) out.push(`busy ${blockEnd[i]}`); else if (i + 1 < n) out.push(`free ${S[i + 1]}`); else out.push("free none");}console.log(out.join("\n"));
JavaMain.java · 46 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int n; static int[] S, E; // 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1) static int lastStartAtMost(int t) { int lo = 0, hi = n; // S[0..lo)는 t 이하, S[hi..n)은 t 초과 while (lo < hi) { int mid = (lo + hi) >>> 1; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1; } public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); S = new int[n]; E = new int[n]; for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); S[i] = Integer.parseInt(st.nextToken()); E[i] = Integer.parseInt(st.nextToken()); } // blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) int[] blockEnd = E.clone(); for (int i = n - 2; i >= 0; i--) if (E[i] == S[i + 1]) blockEnd[i] = blockEnd[i + 1]; st = new StringTokenizer(in.readLine()); StringBuilder out = new StringBuilder(); for (int j = 0; j < q; j++) { int t = Integer.parseInt(st.nextToken()); int i = lastStartAtMost(t); if (i >= 0 && t < E[i]) out.append("busy ").append(blockEnd[i]).append('\n'); else if (i + 1 < n) out.append("free ").append(S[i + 1]).append('\n'); else out.append("free none\n"); } System.out.print(out); }}
C#Main.cs · 35 줄
using System;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]), q = int.Parse(first[1]); int[] S = new int[n], E = new int[n]; for (int i = 0; i < n; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); S[i] = int.Parse(p[0]); E[i] = int.Parse(p[1]); } // blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) int[] blockEnd = (int[])E.Clone(); for (int i = n - 2; i >= 0; i--) if (E[i] == S[i + 1]) blockEnd[i] = blockEnd[i + 1]; string[] qs = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); var sb = new StringBuilder(); for (int j = 0; j < q; j++) { int t = int.Parse(qs[j]); // Array.BinarySearch는 같은 값이 없으면 ~(t보다 큰 첫 자리)를 돌려준다. // 시작 시각은 모두 다르니, 찾으면 그 자리, 못 찾으면 그 앞 자리가 "t 이하인 마지막"이다 int pos = Array.BinarySearch(S, t); int i = pos >= 0 ? pos : ~pos - 1; if (i >= 0 && t < E[i]) sb.Append("busy ").Append(blockEnd[i]).Append('\n'); else if (i + 1 < n) sb.Append("free ").Append(S[i + 1]).Append('\n'); else sb.Append("free none\n"); } Console.Write(sb); }}
C++main.cpp · 27 줄
#include <algorithm>#include <iostream>#include <string>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<int> S(n), E(n); for (int i = 0; i < n; i++) std::cin >> S[i] >> E[i]; // blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) std::vector<int> blockEnd = E; for (int i = n - 2; i >= 0; i--) if (E[i] == S[i + 1]) blockEnd[i] = blockEnd[i + 1]; std::string out; for (int j = 0; j < q; j++) { int t; std::cin >> t; // upper_bound는 t보다 큰 첫 자리. 그 바로 앞이 시작 시각이 t 이하인 마지막 예약이다 int i = int(std::upper_bound(S.begin(), S.end(), t) - S.begin()) - 1; if (i >= 0 && t < E[i]) out += "busy " + std::to_string(blockEnd[i]) + "\n"; else if (i + 1 < n) out += "free " + std::to_string(S[i + 1]) + "\n"; else out += "free none\n"; } std::cout << out;}
Cmain.c · 33 줄
#include <stdio.h>static int S[10000], E[10000], blockEnd[10000];static int n;/* 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1) */int last_start_at_most(int t) { int lo = 0, hi = n; /* S[0..lo)는 t 이하, S[hi..n)은 t 초과 */ while (lo < hi) { int mid = lo + (hi - lo) / 2; if (S[mid] <= t) lo = mid + 1; else hi = mid; } return lo - 1;}int main(void) { int q, t; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d %d", &S[i], &E[i]); /* blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다) */ for (int i = n - 1; i >= 0; i--) { blockEnd[i] = (i + 1 < n && E[i] == S[i + 1]) ? blockEnd[i + 1] : E[i]; } for (int j = 0; j < q; j++) { scanf("%d", &t); int i = last_start_at_most(t); if (i >= 0 && t < E[i]) printf("busy %d\n", blockEnd[i]); else if (i + 1 < n) printf("free %d\n", S[i + 1]); else puts("free none"); } return 0;}
Craykonmain.cray · 58 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];q = 첫줄[1];S = [];E = [];반복 (i = 0; i < n; i++){ p = 콘솔.수들읽기(); S.넣기(p[0]); E.넣기(p[1]);}// blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)blockEnd = E.부분목록(0, n);반복 (i = n - 2; i >= 0; i--){ 만약 (E[i] == S[i + 1]) { blockEnd[i] = blockEnd[i + 1]; }}// 시작 시각이 t 이하인 마지막 예약의 번호(없으면 -1)마지막시작(t){ lo = 0; hi = n; // S[0..lo)는 t 이하, S[hi..n)은 t 초과 동안 (lo < hi) { mid = 수학.몫(lo + hi, 2); // /는 소수까지 나누니 몫을 쓴다 만약 (S[mid] <= t) { lo = mid + 1; } 아니면 { hi = mid; } } 돌려주기 lo - 1;}qs = 콘솔.수들읽기();각각 (t 에서 qs){ i = 마지막시작(t); 만약 (i >= 0 && t < E[i]) { 콘솔.쓰기("busy " + blockEnd[i]); } 아니면 만약 (i + 1 < n) { 콘솔.쓰기("free " + S[i + 1]); } 아니면 { 콘솔.쓰기("free none"); }}