A treatment order that grows more urgent with waiting
An emergency room has k treatment rooms, numbered 1 to k.
n patients are given in order of arrival, numbered 1 to n.
Patient i arrives at minute aᵢ and joins the line, starts with urgency sᵢ, and needs dᵢ minutes of treatment.
The urgency of a patient waiting in line rises by 1 every minute. That is, at minute T patient i's urgency is sᵢ + (T − aᵢ).
At the same minute T, things happen in this order.
① Every room whose treatment ends at minute T becomes free.
② Every patient arriving at minute T joins the line.
③ While there is both a free room and a waiting patient, the free room with the smallest number calls the waiting patient who is most urgent at minute T. If urgencies tie, the patient with the smaller number is called.
A called patient starts treatment at minute T and finishes at minute T + dᵢ, and the room calls no one else in the meantime.
At the start (before minute 0) every room is free.
On the first line print the patient numbers in the order they are called.
On the second line print the total waiting time of all patients (start of treatment − arrival).
On the third line print how many patients each room treated, from room 1 to room k.
Input
The first line has n and k, and the next n lines give patient i's "aᵢ sᵢ dᵢ" separated by single spaces. 1 ≤ n ≤ 10,000, 1 ≤ k ≤ 100, 0 ≤ a₁ ≤ a₂ ≤ … ≤ aₙ ≤ 1,000,000, 1 ≤ sᵢ ≤ 1,000,000, 1 ≤ dᵢ ≤ 10,000. All are integers
Output
Three lines: the n patient numbers in calling order, the total waiting time (plain digits, no commas), and the k patient counts per room. Numbers on a line are separated by single spaces
Example 1 · stdin
5 2
0 3 4
0 5 2
1 4 3
2 6 5
2 5 1
stdout
2 1 4 3 5
8
3 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
Urgency changes every minute, so it seems it cannot live in a heap, but everyone waiting rises at the same speed (1 per minute), so the order of two patients is fixed by sᵢ − aᵢ regardless of T: sᵢ + (T − aᵢ) > sⱼ + (T − aⱼ) ⇔ sᵢ − aᵢ > sⱼ − aⱼ. So three heaps do it: waiting patients (larger s − a first, then smaller number), free rooms (smaller number first) and busy rooms (earlier end first). The next minute when anything changes is the earlier of 'the next patient's arrival' and 'the earliest treatment end', so jump to that minute and do ① ② ③. Scanning the whole line each time is n², too slow for Python and Craykon. Example: at minute 4, patients 3 (4 + 3 = 7) and 5 (5 + 2 = 7) tie, so the smaller number 3 is called. At minute 7 both rooms become free and room 1 calls patient 5. Trap one: forgetting the waiting time and looking only at sᵢ calls patient 5 before patient 3, which is wrong. Trap two: calling the later number on a tie is wrong. Trap three: choosing free rooms 'first freed first' (a queue) is wrong — it is the smallest number. Trap four: doing ③ before ② pushes back a more urgent patient who arrives at the very minute a room frees. Trap five: when 10,000 patients crowd one room, the total wait is about 5×10^11, past a 32-bit int (C/C++ long long, Java/C# long). Heaps differ by language: Python heapq pops the smallest, so push (-(s − a), number) tuples; Java PriorityQueue with Comparator.comparingInt(...).thenComparingInt(...); C# PriorityQueue<TElement, TPriority> with a (-(s − a), number) tuple priority (smallest first); C++ std::priority_queue pops the largest, so flip it with std::greater; JavaScript, TypeScript and C have no heap, so you write one. Craykon also needs a hand-written heap, and since lists cannot be compared it packs one number such as (1000000 − (s − a)) × 100000 + number — if the multiplier is smaller than the numbers (× 1000), a number like 9,999 mixes with the digits in front. The packed number goes up to 2×10^11, within 2^53.
Pythonmain.py · 39 lines
import sysimport heapqdata = sys.stdin.buffer.read().split()n, k = int(data[0]), int(data[1])arrive = [0] * nsev = [0] * ndur = [0] * nfor i in range(n): arrive[i], sev[i], dur[i] = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])# 기다리는 사람의 급한 정도는 s + (T - a)인데, 모두 1분에 1씩 함께 오르니# 두 사람의 차례는 T와 상관없이 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람이 먼저waiting = [] # (-(s - a), 번호)free = list(range(1, k + 1)) # 빈 진료실 번호(가장 작은 것이 맨 위)busy = [] # (끝나는 시각, 진료실 번호)order = []seen = [0] * (k + 1)total_wait = 0nxt = 0 # 아직 오지 않은 첫 환자while len(order) < n: # 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 t = min(arrive[nxt] if nxt < n else float("inf"), busy[0][0] if busy else float("inf")) while busy and busy[0][0] == t: # ① 진료가 끝난 방부터 빈다 heapq.heappush(free, heapq.heappop(busy)[1]) while nxt < n and arrive[nxt] == t: # ② 그 시각에 온 환자가 줄에 선다 heapq.heappush(waiting, (-(sev[nxt] - arrive[nxt]), nxt)) nxt += 1 while free and waiting: # ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 room = heapq.heappop(free) _, p = heapq.heappop(waiting) order.append(p + 1) seen[room] += 1 total_wait += t - arrive[p] heapq.heappush(busy, (t + dur[p], room))print(" ".join(map(str, order)))print(total_wait)print(" ".join(map(str, seen[1:])))
JavaScriptmain.js · 84 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 작은 것이 맨 위에 오는 이진 힙. less(x, y)가 참이면 x가 y보다 먼저 나온다class Heap { constructor(less) { this.a = []; this.less = less; } get size() { return this.a.length; } top() { return this.a[0]; } push(x) { const a = this.a; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (!this.less(a[i], a[p])) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop() { const a = this.a; const top = a[0]; const last = a.pop(); if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let m = i; if (l < a.length && this.less(a[l], a[m])) m = l; if (r < a.length && this.less(a[r], a[m])) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}const [n, k] = data;const arrive = [];const sev = [];const dur = [];for (let i = 0; i < n; i++) { arrive.push(data[2 + 3 * i]); sev.push(data[3 + 3 * i]); dur.push(data[4 + 3 * i]);}// 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람const key = (p) => sev[p] - arrive[p];const waiting = new Heap((x, y) => key(x) > key(y) || (key(x) === key(y) && x < y));const free = new Heap((x, y) => x < y); // 빈 진료실 번호const busy = new Heap((x, y) => x[0] < y[0] || (x[0] === y[0] && x[1] < y[1])); // [끝나는 시각, 진료실]for (let r = 1; r <= k; r++) free.push(r);const order = [];const seen = new Array(k + 1).fill(0);let totalWait = 0;let next = 0; // 아직 오지 않은 첫 환자while (order.length < n) { // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 const t = Math.min(next < n ? arrive[next] : Infinity, busy.size > 0 ? busy.top()[0] : Infinity); while (busy.size > 0 && busy.top()[0] === t) free.push(busy.pop()[1]); // ① 진료가 끝난 방부터 빈다 while (next < n && arrive[next] === t) waiting.push(next++); // ② 그 시각에 온 환자가 줄에 선다 while (free.size > 0 && waiting.size > 0) { // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 const room = free.pop(); const p = waiting.pop(); order.push(p + 1); seen[room]++; totalWait += t - arrive[p]; busy.push([t + dur[p], room]); }}console.log([order.join(" "), totalWait, seen.slice(1).join(" ")].join("\n"));
TypeScriptmain.ts · 85 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 작은 것이 맨 위에 오는 이진 힙. less(x, y)가 참이면 x가 y보다 먼저 나온다class Heap<T> { private readonly a: T[] = []; constructor(private readonly less: (x: T, y: T) => boolean) {} get size(): number { return this.a.length; } top(): T { return this.a[0]; } push(x: T): void { const a = this.a; a.push(x); let i = a.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (!this.less(a[i], a[p])) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } } pop(): T { const a = this.a; const top = a[0]; const last = a.pop() as T; if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let m = i; if (l < a.length && this.less(a[l], a[m])) m = l; if (r < a.length && this.less(a[r], a[m])) m = r; if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } } return top; }}const [n, k] = data;const arrive: number[] = [];const sev: number[] = [];const dur: number[] = [];for (let i = 0; i < n; i++) { arrive.push(data[2 + 3 * i]); sev.push(data[3 + 3 * i]); dur.push(data[4 + 3 * i]);}// 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람const key = (p: number): number => sev[p] - arrive[p];const waiting = new Heap<number>((x, y) => key(x) > key(y) || (key(x) === key(y) && x < y));const free = new Heap<number>((x, y) => x < y); // 빈 진료실 번호type Busy = [end: number, room: number];const busy = new Heap<Busy>((x, y) => x[0] < y[0] || (x[0] === y[0] && x[1] < y[1]));for (let r = 1; r <= k; r++) free.push(r);const order: number[] = [];const seen: number[] = new Array<number>(k + 1).fill(0);let totalWait = 0;let next = 0; // 아직 오지 않은 첫 환자while (order.length < n) { // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 const t = Math.min(next < n ? arrive[next] : Infinity, busy.size > 0 ? busy.top()[0] : Infinity); while (busy.size > 0 && busy.top()[0] === t) free.push(busy.pop()[1]); // ① 진료가 끝난 방부터 빈다 while (next < n && arrive[next] === t) waiting.push(next++); // ② 그 시각에 온 환자가 줄에 선다 while (free.size > 0 && waiting.size > 0) { // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 const room = free.pop(); const p = waiting.pop(); order.push(p + 1); seen[room]++; totalWait += t - arrive[p]; busy.push([t + dur[p], room]); }}console.log([order.join(" "), totalWait, seen.slice(1).join(" ")].join("\n"));
JavaMain.java · 52 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int k = (int) st.nval; int[] arrive = new int[n], sev = new int[n], dur = new int[n]; for (int i = 0; i < n; i++) { st.nextToken(); arrive[i] = (int) st.nval; st.nextToken(); sev[i] = (int) st.nval; st.nextToken(); dur[i] = (int) st.nval; } // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람 PriorityQueue<Integer> waiting = new PriorityQueue<>( Comparator.comparingInt((Integer p) -> -(sev[p] - arrive[p])).thenComparingInt(p -> p)); PriorityQueue<Integer> free = new PriorityQueue<>(); // 빈 진료실 번호 // {끝나는 시각, 진료실}: 시각이 이르고, 같으면 방 번호가 작은 것이 먼저 PriorityQueue<int[]> busy = new PriorityQueue<>((x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1])); for (int r = 1; r <= k; r++) free.add(r); StringBuilder order = new StringBuilder(); int[] seen = new int[k + 1]; long totalWait = 0; // 5×10^11까지 가서 int로는 넘친다 int called = 0, next = 0; while (called < n) { // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 int t = Integer.MAX_VALUE; if (next < n) t = arrive[next]; if (!busy.isEmpty()) t = Math.min(t, busy.peek()[0]); while (!busy.isEmpty() && busy.peek()[0] == t) free.add(busy.poll()[1]); // ① 진료가 끝난 방부터 빈다 while (next < n && arrive[next] == t) waiting.add(next++); // ② 그 시각에 온 환자가 줄에 선다 while (!free.isEmpty() && !waiting.isEmpty()) { // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 int room = free.poll(); int p = waiting.poll(); if (called++ > 0) order.append(' '); order.append(p + 1); seen[room]++; totalWait += t - arrive[p]; busy.add(new int[] {t + dur[p], room}); } } StringBuilder sb = new StringBuilder(); sb.append(order).append('\n').append(totalWait).append('\n'); for (int r = 1; r <= k; r++) sb.append(seen[r]).append(r < k ? ' ' : '\n'); System.out.print(sb); }}
C#Main.cs · 63 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), k = int.Parse(data[1]); var arrive = new int[n]; var sev = new int[n]; var dur = new int[n]; for (int i = 0; i < n; i++) { arrive[i] = int.Parse(data[2 + 3 * i]); sev[i] = int.Parse(data[3 + 3 * i]); dur[i] = int.Parse(data[4 + 3 * i]); } // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람 // PriorityQueue는 우선순위가 작은 것부터 꺼내니 (-(s - a), 번호)를 우선순위로 준다 var waiting = new PriorityQueue<int, (int, int)>(); var free = new PriorityQueue<int, int>(); // 빈 진료실 번호 var busy = new PriorityQueue<int, (int, int)>(); // 진료실, 우선순위 (끝나는 시각, 진료실) for (int r = 1; r <= k; r++) free.Enqueue(r, r); var order = new List<int>(); var seen = new int[k + 1]; long totalWait = 0; // 5×10^11까지 가서 int로는 넘친다 int next = 0; while (order.Count < n) { // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 int t = int.MaxValue; if (next < n) t = arrive[next]; if (busy.TryPeek(out _, out var b)) t = Math.Min(t, b.Item1); while (busy.TryPeek(out int done, out var e) && e.Item1 == t) // ① 진료가 끝난 방부터 빈다 { busy.Dequeue(); free.Enqueue(done, done); } while (next < n && arrive[next] == t) // ② 그 시각에 온 환자가 줄에 선다 { waiting.Enqueue(next, (-(sev[next] - arrive[next]), next)); next++; } while (free.Count > 0 && waiting.Count > 0) // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 { int room = free.Dequeue(); int p = waiting.Dequeue(); order.Add(p + 1); seen[room]++; totalWait += t - arrive[p]; busy.Enqueue(room, (t + dur[p], room)); } } var sb = new StringBuilder(); sb.Append(string.Join(' ', order)).Append('\n').Append(totalWait).Append('\n'); for (int r = 1; r <= k; r++) sb.Append(seen[r]).Append(r < k ? ' ' : '\n'); Console.Write(sb); }}
C++main.cpp · 56 lines
#include <algorithm>#include <cstdint>#include <functional>#include <iostream>#include <queue>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, k; std::cin >> n >> k; std::vector<int> arrive(n), sev(n), dur(n); for (int i = 0; i < n; i++) std::cin >> arrive[i] >> sev[i] >> dur[i]; // priority_queue는 큰 것이 위다: std::greater를 주면 작은 것이 위 using P = std::pair<int, int>; using MinHeap = std::priority_queue<P, std::vector<P>, std::greater<P>>; // 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람 MinHeap waiting; // (-(s - a), 번호) MinHeap busy; // (끝나는 시각, 진료실) std::priority_queue<int, std::vector<int>, std::greater<int>> freeRooms; // 빈 진료실 번호 for (int r = 1; r <= k; r++) freeRooms.push(r); std::vector<int> order; std::vector<int> seen(k + 1, 0); long long totalWait = 0; // 5×10^11까지 가서 int로는 넘친다 int next = 0; while (static_cast<int>(order.size()) < n) { // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 int t = next < n ? arrive[next] : INT32_MAX; if (!busy.empty()) t = std::min(t, busy.top().first); while (!busy.empty() && busy.top().first == t) { // ① 진료가 끝난 방부터 빈다 freeRooms.push(busy.top().second); busy.pop(); } while (next < n && arrive[next] == t) { // ② 그 시각에 온 환자가 줄에 선다 waiting.push({-(sev[next] - arrive[next]), next}); next++; } while (!freeRooms.empty() && !waiting.empty()) { // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 int room = freeRooms.top(); freeRooms.pop(); int p = waiting.top().second; waiting.pop(); order.push_back(p + 1); seen[room]++; totalWait += t - arrive[p]; busy.push({t + dur[p], room}); } } for (int i = 0; i < n; i++) std::cout << order[i] << (i + 1 < n ? ' ' : '\n'); std::cout << totalWait << '\n'; for (int r = 1; r <= k; r++) std::cout << seen[r] << (r < k ? ' ' : '\n');}
Cmain.c · 78 lines
#include <stdio.h>#define MAXN 10000#define MAXK 100/* 작은 것이 맨 위에 오는 이진 힙. 비교할 값을 long long 하나로 만들어 넣는다 */typedef struct { long long a[MAXN + MAXK]; int size;} Heap;static void push(Heap *h, long long x) { int i = h->size++; h->a[i] = x; while (i > 0) { int p = (i - 1) / 2; if (h->a[p] <= h->a[i]) break; long long t = h->a[p]; h->a[p] = h->a[i]; h->a[i] = t; i = p; }}static long long pop(Heap *h) { long long top = h->a[0]; h->a[0] = h->a[--h->size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, m = i; if (l < h->size && h->a[l] < h->a[m]) m = l; if (r < h->size && h->a[r] < h->a[m]) m = r; if (m == i) break; long long t = h->a[m]; h->a[m] = h->a[i]; h->a[i] = t; i = m; } return top;}static int arrive[MAXN], sev[MAXN], dur[MAXN], order[MAXN], seen[MAXK + 1];static Heap waiting, freeRooms, busy;int main(void) { int n, k; if (scanf("%d %d", &n, &k) != 2) return 0; for (int i = 0; i < n; i++) scanf("%d %d %d", &arrive[i], &sev[i], &dur[i]); /* 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람. s - a는 -10^6 ~ 10^6이라 (10^6 - (s - a)) * 100000 + 번호가 작을수록 먼저다 */ /* 바쁜 방은 끝나는 시각 * 1000 + 방 번호(끝나는 시각은 1.01×10^8까지) */ for (int r = 1; r <= k; r++) push(&freeRooms, r); long long totalWait = 0; /* 5×10^11까지 가서 int로는 넘친다 */ int called = 0, next = 0; while (called < n) { /* 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 */ long long t = next < n ? arrive[next] : -1; if (busy.size > 0 && (t < 0 || busy.a[0] / 1000 < t)) t = busy.a[0] / 1000; while (busy.size > 0 && busy.a[0] / 1000 == t) push(&freeRooms, pop(&busy) % 1000); /* ① 진료가 끝난 방부터 빈다 */ while (next < n && arrive[next] == t) { /* ② 그 시각에 온 환자가 줄에 선다 */ push(&waiting, (1000000LL - (sev[next] - arrive[next])) * 100000 + next); next++; } while (freeRooms.size > 0 && waiting.size > 0) { /* ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 */ int room = (int)pop(&freeRooms); int p = (int)(pop(&waiting) % 100000); order[called++] = p + 1; seen[room]++; totalWait += t - arrive[p]; push(&busy, (t + dur[p]) * 1000 + room); } } for (int i = 0; i < n; i++) printf("%d%c", order[i], i + 1 < n ? ' ' : '\n'); printf("%lld\n", totalWait); for (int r = 1; r <= k; r++) printf("%d%c", seen[r], r < k ? ' ' : '\n'); return 0;}
Craykonmain.cray · 121 lines
// 작은 수가 맨 위에 오는 최소 힙(목록 heap). heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.Add(x); i = heap.Count - 1; while (i > 0) { 부모 = Mathf.Quot(i - 1, 2); if (heap[부모] <= heap[i]) { break; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙빼기(heap){ top = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); i = 0; while (true) { l = 2 * i + 1; r = l + 1; small = i; if (l < heap.Count && heap[l] < heap[small]) { small = l; } if (r < heap.Count && heap[r] < heap[small]) { small = r; } if (small == i) { break; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; } return top;}첫줄 = Console.ReadNumbers();n = 첫줄[0];k = 첫줄[1];arrive = [];sev = [];dur = [];for (i = 0; i < n; i++){ p = Console.ReadNumbers(); arrive.Add(p[0]); sev.Add(p[1]); dur.Add(p[2]);}// 급한 정도 s + (T - a)는 모두 1분에 1씩 함께 오르니 차례는 s - a로 정해진다: 큰 것이 먼저, 같으면 번호가 작은 사람// 힙에는 수 하나만 넣는다: (1000000 - (s - a)) * 100000 + 번호 — 작을수록 먼저(2×10^11까지라 정확하다)waiting = [];// 바쁜 방: 끝나는 시각 * 1000 + 방 번호(끝나는 시각은 1.01×10^8까지)busy = [];free = []; // 빈 진료실 번호for (r = 1; r <= k; r++){ 힙넣기(free, r);}order = [];seen = NewList(k + 1, 0);totalWait = 0;next = 0; // 아직 오지 않은 첫 환자while (order.Count < n){ // 다음에 무엇인가 바뀌는 시각: 다음 환자가 오거나 진료가 끝날 때 t = -1; if (next < n) { t = arrive[next]; } if (busy.Count > 0) { 끝 = Mathf.Quot(busy[0], 1000); if (t < 0 || 끝 < t) { t = 끝; } } // ① 진료가 끝난 방부터 빈다 while (busy.Count > 0 && Mathf.Quot(busy[0], 1000) == t) { 힙넣기(free, 힙빼기(busy) % 1000); } // ② 그 시각에 온 환자가 줄에 선다 while (next < n && arrive[next] == t) { 힙넣기(waiting, (1000000 - (sev[next] - arrive[next])) * 100000 + next); next += 1; } // ③ 번호가 작은 빈 방부터 가장 급한 사람을 부른다 while (free.Count > 0 && waiting.Count > 0) { room = 힙빼기(free); p = 힙빼기(waiting) % 100000; order.Add(p + 1); seen[room] += 1; totalWait += t - arrive[p]; 힙넣기(busy, (t + dur[p]) * 1000 + room); }}Console.WriteLine(order.Join(" "));Console.WriteLine(totalWait);seen.RemoveAt(0);Console.WriteLine(seen.Join(" "));