You are given the n bookings of one meeting room for a day and q questions.
Times are non-negative integers.
The first line gives n and q.
Each of the next n lines gives one booking in the form "s e". This booking uses the room from time s until just before e. So at time s the room is in use, and at time e it is not in use by this booking.
The bookings are given in order of start time, and they do not overlap.
However, a booking may start exactly when the previous one ends. Such bookings are said to touch.
The last line gives q times t to ask about, separated by spaces.
For each question, print the answer on one line.
If some booking uses the room at time t, print "busy X". X is the first time the room becomes free after that booking and all the bookings that follow it touching one another have ended.
If no booking uses the room at time t, print "free Y". Y is the start time of the earliest booking that starts after t.
If no booking starts after t, print "free none".
There are many bookings and questions, so do not scan the bookings from the start for each question; search by halving instead.
Input
1 ≤ n ≤ 10,000, 1 ≤ q ≤ 10,000, 0 ≤ s < e ≤ 1,000,000,000, e of a booking ≤ s of the next booking, 0 ≤ t ≤ 1,000,000,000
Output
One line per question: busy X, free Y or free none
Example 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
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
Each language has a different tool for searching a sorted array. Python bisect.bisect_right(S, t) and C++ std::upper_bound give the first position greater than t, so the one just before it is "the last booking starting at or before t". Java Arrays.binarySearch and C# Array.BinarySearch return the position when they find an equal value, and a negative number -(insertion point) - 1 when they don't (in C#, ~pos recovers the insertion point). With several equal values they do not promise which position you get, but here every start time is different, so they work. JS/TS and Craykon have no such function, and C's bsearch only finds an equal value, so you write it yourself. Keep lo and hi so that "S[0..lo) are at most t and S[hi..n) are greater than t", and when the loop ends lo - 1 is the answer. Craykon and JS / divide into decimals, so find the middle with Mathf.Quot(lo + hi, 2) or >> 1. The first trap is the boundaries. bisect_left (the position before equal values) misses the booking when t equals its start time. A booking lasts until just before e, so when t == e it is not in use by that booking; the test is t < E[i]. The second trap is a t earlier than the first booking. The index you find is -1, and in Python E[-1] is not an error but the last booking, so it wrongly says busy. Java, C# and Craykon stop with an out-of-range error, JS/TS get undefined so the comparison is always false, and C/C++ have undefined behavior, so ask i >= 0 first. Third, following touching bookings for every question is slow when the chain is long, so fill in "the first free time from here on" once, from the back.
Pythonmain.py · 25 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];q = 첫줄[1];S = [];E = [];for (i = 0; i < n; i++){ p = Console.ReadNumbers(); S.Add(p[0]); E.Add(p[1]);}// blockEnd[i]: i번 예약부터 맞닿은 예약을 따라가다 처음 비는 시각(뒤에서부터 채운다)blockEnd = E.GetRange(0, n);for (i = n - 2; i >= 0; i--){ if (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 초과 while (lo < hi) { mid = Mathf.Quot(lo + hi, 2); // /는 소수까지 나누니 몫을 쓴다 if (S[mid] <= t) { lo = mid + 1; } else { hi = mid; } } return lo - 1;}qs = Console.ReadNumbers();foreach (t in qs){ i = 마지막시작(t); if (i >= 0 && t < E[i]) { Console.WriteLine("busy " + blockEnd[i]); } else if (i + 1 < n) { Console.WriteLine("free " + S[i + 1]); } else { Console.WriteLine("free none"); }}