Choosing 3D printer orders that meet their deadlines
One 3D printer has received n print orders.
The i-th order takes t hours to print and must be finished by time d.
The printer can be used from time 0, prints one order at a time, and prints an order to the end without stopping once it starts.
An order finishing exactly at time d meets its deadline.
You choose some of the orders so that every chosen order finishes by its deadline.
The chosen orders may be printed in any order you like, and orders not chosen are not printed.
Make the number of chosen orders as large as possible.
If several choices do that, pick the one whose total printing time is smallest.
Print the number of chosen orders and their total printing time on one line, separated by a space.
If no order can be chosen, print 0 0.
Input
The first line has n; each of the next n lines has t and d separated by a space. 1 ≤ n ≤ 10,000, 1 ≤ t ≤ 1,000,000, 1 ≤ d ≤ 10,000,000,000
Output
The number of chosen orders and their total printing time on one line, separated by a space
Example 1 · stdin
5
4 4
1 5
1 5
1 6
1 6
stdout
4 4
Example 2 · stdin
2
5 3
7 6
stdout
0 0
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
The chosen orders are best printed back to back earliest deadline first. So sort the orders by deadline and add them one by one; when the running total passes the current deadline, remove the longest chosen order (greedy — the count drops by one, but the time left drops the most). Taking out the longest quickly needs a max-heap. What remains is a choice with the most orders and, among those, the smallest total time. Trap one: just skipping an order that does not fit is wrong — in the first example, keeping the 4-hour order lets only two 1-hour orders in (3 in all), but dropping it gives 4. Trap two: adding shortest orders first lets a short order with a late deadline take the place of an order with an early deadline. Trap three: the total reaches 10 billion and deadlines exceed int too, so C and C++ need long long, Java and C# long (a Java or C# int wraps around to a negative number past about 2.1 billion. Python, JavaScript, TypeScript and Craykon work as they are — far below 2^53). Trap four: getting a max-heap is opposite between languages. C++ std::priority_queue is a max-heap by default, so use it as is; Java PriorityQueue is a min-heap by default, so it needs Collections.reverseOrder() (without it, the shortest order is removed). Python heapq only has a min-heap, so push -t and flip the sign of what comes out; C# PriorityQueue<long, long> gets the priority -t. JavaScript, TypeScript, C and Craykon build the heap on a list and flip the comparison so a parent is greater than or equal to its children (the parent index is Mathf.Quot(i - 1, 2) in Craykon). The sort rule is written differently too: C qsort's compare function returns an int, so instead of subtracting long long deadlines use (a > b) - (a < b); Craykon passes jobs.Sort(byDeadline) a function that returns x[1] - y[1] (numbers are doubles, so subtracting is fine).
Pythonmain.py · 17 lines
import heapqimport sysdata = sys.stdin.read().split()n = int(data[0])jobs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)] # (걸리는 시간, 마감)jobs.sort(key=lambda job: job[1]) # 마감이 이른 것부터chosen = [] # 고른 주문의 시간들. heapq는 최소 힙이라 음수로 넣어 가장 긴 것을 꺼낸다total = 0 # 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각for t, d in jobs: heapq.heappush(chosen, -t) total += t if total > d: total += heapq.heappop(chosen) # 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다print(len(chosen), total)
JavaScriptmain.js · 55 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];// 최대 힙: heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2class MaxHeap { constructor() { this.items = []; } get size() { return this.items.length; } push(x) { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent] >= a[i]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop() { const a = this.items; const top = a[0]; const last = a.pop(); if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let big = i; if (l < a.length && a[l] > a[big]) big = l; if (r < a.length && a[r] > a[big]) big = r; if (big === i) break; [a[big], a[i]] = [a[i], a[big]]; i = big; } } return top; }}const jobs = []; // [걸리는 시간, 마감]for (let i = 0; i < n; i++) jobs.push([data[1 + 2 * i], data[2 + 2 * i]]);jobs.sort((x, y) => x[1] - y[1]); // 마감이 이른 것부터const chosen = new MaxHeap(); // 고른 주문의 시간들let total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각for (const [t, d] of jobs) { chosen.push(t); total += t; if (total > d) total -= chosen.pop(); // 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다}console.log(`${chosen.size} ${total}`);
TypeScriptmain.ts · 58 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];// 최대 힙: heap[0]이 가장 크고, i의 자식은 2i+1, 2i+2class MaxHeap { private items: number[] = []; get size(): number { return this.items.length; } push(x: number): void { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent] >= a[i]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop(): number { const a = this.items; const top = a[0]; const last = a.pop()!; // size > 0일 때만 부른다 if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let big = i; if (l < a.length && a[l] > a[big]) big = l; if (r < a.length && a[r] > a[big]) big = r; if (big === i) break; [a[big], a[i]] = [a[i], a[big]]; i = big; } } return top; }}const jobs: [time: number, deadline: number][] = [];for (let i = 0; i < n; i++) jobs.push([data[1 + 2 * i], data[2 + 2 * i]]);jobs.sort((x, y) => x[1] - y[1]); // 마감이 이른 것부터const chosen = new MaxHeap(); // 고른 주문의 시간들let total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각for (const [t, d] of jobs) { chosen.push(t); total += t; if (total > d) total -= chosen.pop(); // 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다}console.log(`${chosen.size} ${total}`);
JavaMain.java · 30 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Collections;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); long[][] jobs = new long[n][]; // {걸리는 시간, 마감}. 마감은 int를 넘는다 for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); jobs[i] = new long[] {Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())}; } Arrays.sort(jobs, (x, y) -> Long.compare(x[1], y[1])); // 마감이 이른 것부터 // PriorityQueue는 기본이 최소 힙이라 reverseOrder()로 가장 긴 것이 먼저 나오게 한다 PriorityQueue<Long> chosen = new PriorityQueue<>(Collections.reverseOrder()); long total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각 for (long[] job : jobs) { chosen.add(job[0]); total += job[0]; if (total > job[1]) total -= chosen.poll(); // 마감을 넘으면 가장 긴 주문을 뺀다 } System.out.println(chosen.size() + " " + total); }}
C#Main.cs · 28 lines
using System;using System.Collections.Generic;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); var jobs = new (long t, long d)[n]; // 마감은 int를 넘는다 for (int i = 0; i < n; i++) { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); jobs[i] = (long.Parse(p[0]), long.Parse(p[1])); } Array.Sort(jobs, (x, y) => x.d.CompareTo(y.d)); // 마감이 이른 것부터 // PriorityQueue는 우선순위가 작은 것부터 나온다 → 우선순위를 -t로 주면 가장 긴 것이 먼저 var chosen = new PriorityQueue<long, long>(); long total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각 foreach (var (t, d) in jobs) { chosen.Enqueue(t, -t); total += t; if (total > d) total -= chosen.Dequeue(); // 마감을 넘으면 가장 긴 주문을 뺀다 } Console.WriteLine($"{chosen.Count} {total}"); }}
C++main.cpp · 27 lines
#include <algorithm>#include <iostream>#include <queue>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<std::pair<long long, long long>> jobs(n); // (마감, 걸리는 시간). 마감은 int를 넘는다 for (auto& [d, t] : jobs) std::cin >> t >> d; std::sort(jobs.begin(), jobs.end()); // 마감이 이른 것부터 std::priority_queue<long long> chosen; // 기본이 최대 힙: top()이 가장 긴 주문 long long total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각 for (auto [d, t] : jobs) { chosen.push(t); total += t; if (total > d) { // 마감을 넘으면 가장 긴 주문을 뺀다 total -= chosen.top(); chosen.pop(); } } std::cout << chosen.size() << " " << total << "\n";}
Cmain.c · 63 lines
#include <stdio.h>#include <stdlib.h>#define MAXN 10000typedef struct { long long t, d; /* 걸리는 시간, 마감(int를 넘는다) */} Job;static Job jobs[MAXN];static long long heap[MAXN]; /* 최대 힙: heap[0]이 가장 크다 */static int heap_size = 0;static int by_deadline(const void* x, const void* y) { long long a = ((const Job*)x)->d, b = ((const Job*)y)->d; return (a > b) - (a < b); /* 빼면 int를 넘을 수 있어 비교로 */}static void swap(long long* x, long long* y) { long long t = *x; *x = *y; *y = t;}static void heap_push(long long x) { int i = heap_size++; heap[i] = x; while (i > 0 && heap[(i - 1) / 2] < heap[i]) { swap(&heap[(i - 1) / 2], &heap[i]); i = (i - 1) / 2; }}static long long heap_pop(void) { long long top = heap[0]; heap[0] = heap[--heap_size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, big = i; if (l < heap_size && heap[l] > heap[big]) big = l; if (r < heap_size && heap[r] > heap[big]) big = r; if (big == i) break; swap(&heap[big], &heap[i]); i = big; } return top;}int main(void) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lld %lld", &jobs[i].t, &jobs[i].d); qsort(jobs, n, sizeof(Job), by_deadline); /* 마감이 이른 것부터 */ long long total = 0; /* 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각 */ for (int i = 0; i < n; i++) { heap_push(jobs[i].t); total += jobs[i].t; if (total > jobs[i].d) total -= heap_pop(); /* 마감을 넘으면 가장 긴 주문을 뺀다 */ } printf("%d %lld\n", heap_size, total); return 0;}
Craykonmain.cray · 76 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;}// 정렬 기준: 마감이 이른 주문이 앞byDeadline(x, y){ return x[1] - y[1];}n = Console.ReadNumbers()[0];jobs = []; // [걸리는 시간, 마감]for (i = 0; i < n; i++){ jobs.Add(Console.ReadNumbers());}jobs.Sort(byDeadline);chosen = []; // 고른 주문의 시간들(최대 힙)total = 0; // 고른 주문을 마감 순으로 이어 뽑으면 마지막이 끝나는 시각foreach (job in jobs){ 힙넣기(chosen, job[0]); total += job[0]; if (total > job[1]) { total -= 힙꺼내기(chosen); // 마감을 넘으면 고른 것 가운데 가장 긴 주문을 뺀다 }}Console.WriteLine(chosen.Count + " " + total);