A village festival is planning its all-night watch. The night is divided into L time slots numbered 1 to L. n volunteers each offered a span they can stand. Volunteer i offered to stand from slot sᵢ to slot eᵢ, including both end slots. A chosen volunteer stands the whole offered span. You cannot use only part of a span. Every time slot must have at least k chosen people standing. Volunteers who offered the same span are different people and count separately. Print the minimum number of volunteers to choose. If some slot has fewer than k people even when every volunteer is chosen, print the lowest-numbered such slot.
Input
The first line has the number of volunteers n (1 ≤ n ≤ 10,000), the number of time slots L (1 ≤ L ≤ 1,000,000,000) and the number of people needed per slot k (1 ≤ k ≤ 5), separated by single spaces. Line i of the next n lines has integers sᵢ and eᵢ (1 ≤ sᵢ ≤ eᵢ ≤ L), separated by a single space. The volunteers are given in no particular order.
Output
If every slot can have at least k people, print the minimum number of volunteers to choose on one line. Otherwise print -1 and the lowest-numbered slot that has fewer than k people even when every volunteer is chosen, separated by a single space, on one line. Print numbers without commas.
Example 1 · stdin
6 10 2
1 4
1 6
3 10
5 8
2 3
7 10
stdout
4
Example 2 · stdin
4 8 2
1 5
1 3
4 8
7 8
stdout
-1 6
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
This is a greedy problem. Look at x, the first slot that does not yet have k people. Only people who start at or before slot x can stand there. Everything before x is already full, so whoever we pick, picking the one who stays the longest never hurts. So sort the volunteers by start slot and push the end slot of everyone whose start is at most x into a max-heap. Pop as many as slot x lacks. Until the chosen person who ends first leaves, the k people stay, so jump x to that end slot + 1. L is a billion, so you cannot walk slot by slot. In the first example, at x = 1 the candidates are (1, 4) and (1, 6), and both are chosen. The earlier end is 4, so x = 5. At slot 5 only the person ending at 6 remains, so one is missing; among the candidates (3, 10), (5, 8), (2, 3) the latest-ending (3, 10) is chosen. At x = 7 one is missing again, (7, 10) is chosen, and two people last to the end: the answer is 4. In the second example only (4, 8) can stand at slot 6, so the answer is -1 6. If the end slot on top of the heap is less than x, nobody else can stand at x. Trap 1: do not pick the one who started first. Choosing (2, 3) or (5, 8) at slot 5 of the first example costs more people. Trap 2: peeking at the top of the heap without popping counts one person several times. A person can be chosen only once. Trap 3: the common single-cover solution (remember only the farthest-reaching span) is wrong when k is 2 or more. Candidates that were passed over are needed later, so they must stay in the heap. Trap 4: the next slot to look at is the one after the earliest end among the chosen people. Jumping to the latest end skips slots that lack people in between. Trap 5: the end slot is also stood. Treating a person whose end slot equals x as already gone makes you choose extra people. Trap 6: the input is not in start order. Without sorting, an early volunteer written later is missed. The max-heap differs by language. C++ priority_queue is a max-heap from the start. Python's heapq is only a min-heap, so push negated values; Java's PriorityQueue takes Comparator.reverseOrder(). C#'s PriorityQueue<TElement, TPriority> dequeues the smallest priority first, so use the negated end slot as the priority. JavaScript, TypeScript, C and Craykon have no heap, so build one on an array (list). Craykon grows and shrinks the end of the list with Add and RemoveAt. Take care with sorting too. JavaScript's sort() without a compare function compares as strings and puts 10 before 9. A C qsort comparator is written like (x > y) - (x < y). Craykon passes a list of indexes to Sort(compare) and compares by start slot.
Pythonmain.py · 34 lines
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 lines
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 lines
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 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 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 lines
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 lines
#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 lines
#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 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; big = i; if (l < heap.Count && heap[l] > heap[big]) { big = l; } if (r < heap.Count && heap[r] > heap[big]) { big = r; } if (big == i) { break; } t = heap[big]; heap[big] = heap[i]; heap[i] = t; i = big; } return top;}첫줄 = Console.ReadNumbers();n = 첫줄[0];length = 첫줄[1];k = 첫줄[2];starts = [];ends = [];order = [];for (i = 0; i < n; i++){ 줄 = Console.ReadNumbers(); starts.Add(줄[0]); ends.Add(줄[1]); order.Add(i);}// 시작 칸이 이른 사람부터 보도록 번호를 정렬한다byStart(a, b){ return starts[a] - starts[b];}order.Sort(byStart);cand = []; // 아직 뽑지 않았고 x칸 이전에 시작하는 사람들의 끝 칸(최대 힙)active = []; // 뽑은 사람 가운데 x칸을 지키는 사람들의 끝 칸(많아야 k개)next = 0; // 아직 후보에 넣지 않은 첫 사람chosen = 0;x = 1; // 아직 k명이 채워지지 않은 가장 앞 칸fail = 0;while (x <= length && fail == 0){ while (next < n && starts[order[next]] <= x) { 힙넣기(cand, ends[order[next]]); next += 1; } // x칸보다 먼저 끝난 사람을 뺀다 still = []; foreach (e in active) { if (e >= x) { still.Add(e); } } active = still; // 모자란 만큼, 가장 늦게까지 서는 사람부터 뽑는다 while (active.Count < k) { if (cand.Count == 0 || cand[0] < x) { fail = x; break; } active.Add(힙빼기(cand)); chosen += 1; } if (fail == 0) { // 가장 먼저 끝나는 사람이 빠지는 칸까지는 k명이 그대로 있다 first = active[0]; foreach (e in active) { first = Mathf.Min(first, e); } x = first + 1; }}if (fail > 0){ Console.WriteLine("-1 " + fail);}else{ Console.WriteLine(chosen);}