import heapqimport sysdata = sys.stdin.buffer.read().split()n, length, k = int(data[0]), int(data[1]), int(data[2])shifts = sorted((int(data[3 + 2 * i]), int(data[4 + 2 * i])) for i in range(n))cand = [] # 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙: 부호를 바꿔 넣는다)active = [] # 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)nxt = 0 # 아직 후보에 넣지 않은 첫 사람chosen = 0x = 1 # 아직 k명이 채워지지 않은 가장 앞 칸fail = 0while x <= length: while nxt < n and shifts[nxt][0] <= x: heapq.heappush(cand, -shifts[nxt][1]) nxt += 1 active = [e for e in active if e >= x] # 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while len(active) < k: if not cand or -cand[0] < x: fail = x break active.append(-heapq.heappop(cand)) chosen += 1 if fail: break # 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 x = min(active) + 1if fail: print(-1, fail)else: print(chosen)
JavaScriptmain.js · 60 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const shifts = [];for (let i = 0; i < n; i++) shifts.push([data[3 + 2 * i], data[4 + 2 * i]]);shifts.sort((a, b) => a[0] - b[0]); // 비교 함수가 없으면 문자열로 견주어 10이 9보다 앞에 온다// JavaScript에는 힙이 없어서 배열로 최대 힙을 만든다. i의 자식은 2i+1, 2i+2function heapPush(heap, x) { heap.push(x); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[parent], heap[i]] = [heap[i], heap[parent]]; i = parent; }}function heapPop(heap) { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[big], heap[i]] = [heap[i], heap[big]]; i = big; } } return top;}const cand = []; // 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙)let active = []; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)let next = 0; // 아직 후보에 넣지 않은 첫 사람let chosen = 0;let x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸let fail = 0;while (x <= length && fail === 0) { while (next < n && shifts[next][0] <= x) heapPush(cand, shifts[next++][1]); active = active.filter((e) => e >= x); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.length < k) { if (cand.length === 0 || cand[0] < x) { fail = x; break; } active.push(heapPop(cand)); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail === 0) x = Math.min(...active) + 1;}console.log(fail > 0 ? `-1 ${fail}` : String(chosen));
TypeScriptmain.ts · 62 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const shifts: [number, number][] = [];for (let i = 0; i < n; i++) shifts.push([data[3 + 2 * i], data[4 + 2 * i]]);shifts.sort((a, b) => a[0] - b[0]); // 비교 함수가 없으면 문자열로 견주어 10이 9보다 앞에 온다// TypeScript에도 힙이 없어서 배열로 최대 힙을 만든다. i의 자식은 2i+1, 2i+2function heapPush(heap: number[], x: number): void { heap.push(x); let i = heap.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (heap[parent] >= heap[i]) break; [heap[parent], heap[i]] = [heap[i], heap[parent]]; i = parent; }}function heapPop(heap: number[]): number { const top: number = heap[0]; const last = heap.pop(); if (last !== undefined && heap.length > 0) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1; const r = l + 1; let big = i; if (l < heap.length && heap[l] > heap[big]) big = l; if (r < heap.length && heap[r] > heap[big]) big = r; if (big === i) break; [heap[big], heap[i]] = [heap[i], heap[big]]; i = big; } } return top;}const cand: number[] = []; // 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙)let active: number[] = []; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)let next = 0; // 아직 후보에 넣지 않은 첫 사람let chosen = 0;let x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸let fail = 0;while (x <= length && fail === 0) { while (next < n && shifts[next][0] <= x) heapPush(cand, shifts[next++][1]); active = active.filter((e: number) => e >= x); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.length < k) { if (cand.length === 0 || cand[0] < x) { fail = x; break; } active.push(heapPop(cand)); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail === 0) x = Math.min(...active) + 1;}console.log(fail > 0 ? `-1 ${fail}` : String(chosen));
JavaMain.java · 40 行
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 length = (int) st.nval; st.nextToken(); int k = (int) st.nval; int[][] shifts = new int[n][2]; for (int i = 0; i < n; i++) { st.nextToken(); shifts[i][0] = (int) st.nval; st.nextToken(); shifts[i][1] = (int) st.nval; } Arrays.sort(shifts, (a, b) -> Integer.compare(a[0], b[0])); // PriorityQueue는 최소 힙이라 차례를 뒤집어 최대 힙으로 쓴다 PriorityQueue<Integer> cand = new PriorityQueue<>(Comparator.reverseOrder()); // 아직 뽑지 않은 후보들의 끝 칸 List<Integer> active = new ArrayList<>(); // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) int next = 0, chosen = 0, fail = 0; int x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸 while (x <= length && fail == 0) { while (next < n && shifts[next][0] <= x) cand.add(shifts[next++][1]); final int now = x; active.removeIf(e -> e < now); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.size() < k) { if (cand.isEmpty() || cand.peek() < x) { fail = x; break; } active.add(cand.poll()); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail == 0) x = Collections.min(active) + 1; } System.out.println(fail > 0 ? "-1 " + fail : String.valueOf(chosen)); }}
C#Main.cs · 44 行
using System;using System.Collections.Generic;using System.Linq;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), length = int.Parse(data[1]), k = int.Parse(data[2]); var shifts = new (int Start, int End)[n]; for (int i = 0; i < n; i++) shifts[i] = (int.Parse(data[3 + 2 * i]), int.Parse(data[4 + 2 * i])); Array.Sort(shifts, (a, b) => a.Start.CompareTo(b.Start)); // PriorityQueue는 우선순위가 작은 것부터 꺼내니, 우선순위에 -끝 칸을 넣어 최대 힙으로 쓴다 var cand = new PriorityQueue<int, int>(); // 아직 뽑지 않은 후보들의 끝 칸 var active = new List<int>(); // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) int next = 0, chosen = 0, fail = 0; int x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸 while (x <= length && fail == 0) { while (next < n && shifts[next].Start <= x) { cand.Enqueue(shifts[next].End, -shifts[next].End); next++; } active.RemoveAll(e => e < x); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.Count < k) { if (cand.Count == 0 || cand.Peek() < x) { fail = x; break; } active.Add(cand.Dequeue()); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail == 0) x = active.Min() + 1; } Console.WriteLine(fail > 0 ? $"-1 {fail}" : chosen.ToString()); }}
C++main.cpp · 39 行
#include <algorithm>#include <iostream>#include <queue>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, length, k; cin >> n >> length >> k; vector<pair<int, int>> shifts(n); // (시작 칸, 끝 칸) for (auto &s : shifts) cin >> s.first >> s.second; sort(shifts.begin(), shifts.end()); priority_queue<int> cand; // 아직 뽑지 않은 후보들의 끝 칸. priority_queue는 처음부터 최대 힙이다 vector<int> active; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) int next = 0, chosen = 0, fail = 0; int x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸 while (x <= length && fail == 0) { while (next < n && shifts[next].first <= x) cand.push(shifts[next++].second); active.erase(remove_if(active.begin(), active.end(), [x](int e) { return e < x; }), active.end()); // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while ((int)active.size() < k) { if (cand.empty() || cand.top() < x) { fail = x; break; } active.push_back(cand.top()); cand.pop(); chosen++; } // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 if (fail == 0) x = *min_element(active.begin(), active.end()) + 1; } if (fail > 0) cout << "-1 " << fail << '\n'; else cout << chosen << '\n'; return 0;}
Cmain.c · 87 行
#include <stdio.h>#include <stdlib.h>#define MAXN 10000#define MAXK 5typedef struct { int start, end;} Shift;static Shift shifts[MAXN];static int heap[MAXN]; /* 최대 힙: heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2 */static int heapSize = 0;static int byStart(const void *a, const void *b) { int x = ((const Shift *)a)->start, y = ((const Shift *)b)->start; return (x > y) - (x < y);}static void heapPush(int x) { int i = heapSize++; heap[i] = x; while (i > 0) { int parent = (i - 1) / 2; if (heap[parent] >= heap[i]) break; int t = heap[parent]; heap[parent] = heap[i]; heap[i] = t; i = parent; }}static int heapPop(void) { int top = heap[0]; heap[0] = heap[--heapSize]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, big = i; if (l < heapSize && heap[l] > heap[big]) big = l; if (r < heapSize && heap[r] > heap[big]) big = r; if (big == i) break; int t = heap[big]; heap[big] = heap[i]; heap[i] = t; i = big; } return top;}int main(void) { int n, length, k; if (scanf("%d %d %d", &n, &length, &k) != 3) return 1; for (int i = 0; i < n; i++) scanf("%d %d", &shifts[i].start, &shifts[i].end); qsort(shifts, (size_t)n, sizeof(Shift), byStart); int active[MAXK]; /* 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개) */ int activeCount = 0; int next = 0, chosen = 0, fail = 0; int x = 1; /* 아직 k명이 채워지지 않은 가장 앞 칸 */ while (x <= length && fail == 0) { while (next < n && shifts[next].start <= x) heapPush(shifts[next++].end); /* x칸보다 먼저 끝난 사람을 뺀다 */ int kept = 0; for (int i = 0; i < activeCount; i++) if (active[i] >= x) active[kept++] = active[i]; activeCount = kept; /* 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 */ while (activeCount < k) { if (heapSize == 0 || heap[0] < x) { fail = x; break; } active[activeCount++] = heapPop(); chosen++; } if (fail == 0) { /* 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 */ int first = active[0]; for (int i = 1; i < activeCount; i++) if (active[i] < first) first = active[i]; x = first + 1; } } if (fail > 0) printf("-1 %d\n", fail); else printf("%d\n", chosen); return 0;}
Craykonmain.cray · 127 行
// 큰 수가 맨 위에 오는 최대 힙(목록 heap). heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.追加(x); i = heap.個数 - 1; 間 (i > 0) { 부모 = 数学.商(i - 1, 2); もし (heap[부모] >= heap[i]) { 抜ける; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙빼기(heap){ top = heap[0]; heap[0] = heap[heap.個数 - 1]; heap.位置で取り除く(heap.個数 - 1); i = 0; 間 (真) { l = 2 * i + 1; r = l + 1; big = i; もし (l < heap.個数 && heap[l] > heap[big]) { big = l; } もし (r < heap.個数 && heap[r] > heap[big]) { big = r; } もし (big == i) { 抜ける; } t = heap[big]; heap[big] = heap[i]; heap[i] = t; i = big; } 返す top;}첫줄 = コンソール.数読み();n = 첫줄[0];length = 첫줄[1];k = 첫줄[2];starts = [];ends = [];order = [];繰り返す (i = 0; i < n; i++){ 줄 = コンソール.数読み(); starts.追加(줄[0]); ends.追加(줄[1]); order.追加(i);}// 시작 칸이 이른 사람부터 보도록 번호를 정렬한다byStart(a, b){ 返す starts[a] - starts[b];}order.並べ替え(byStart);cand = []; // 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙)active = []; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)next = 0; // 아직 후보에 넣지 않은 첫 사람chosen = 0;x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸fail = 0;間 (x <= length && fail == 0){ 間 (next < n && starts[order[next]] <= x) { 힙넣기(cand, ends[order[next]]); next += 1; } // x칸보다 먼저 끝난 사람을 뺀다 still = []; それぞれ (e の中 active) { もし (e >= x) { still.追加(e); } } active = still; // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 間 (active.個数 < k) { もし (cand.個数 == 0 || cand[0] < x) { fail = x; 抜ける; } active.追加(힙빼기(cand)); chosen += 1; } もし (fail == 0) { // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 first = active[0]; それぞれ (e の中 active) { first = 数学.小さい方(first, e); } x = first + 1; }}もし (fail > 0){ コンソール.書く("-1 " + fail);}でなければ{ コンソール.書く(chosen);}