Cerinta completa
You have a long list of tasks that you need to do today. To accomplish task you need minutes, and the deadline for this task is . You need not complete a task at a stretch. You can complete a part of it, switch to another task, and then switch back.
You’ve realized that it might not be possible to complete all the tasks by their deadline. So you decide to do them in such a manner that the maximum amount by which a task’s completion time overshoots its deadline is minimized.
Input Format
The first line contains the number of tasks, . Each of the next lines contains two integers, and .
Constraints
Output Format
Output lines. The line contains the value of the maximum amount by which a task’s completion time overshoots its deadline, when the first tasks on your list are scheduled optimally. See the sample input for clarification.
Sample Input
5
2 2
1 1
4 3
10 1
2 1
Sample Output
0
1
2
2
3
Explanation
The first task alone can be completed in 2 minutes, and so you won’t overshoot the deadline.
With the first two tasks, the optimal schedule can be:
time 1: task 2
time 2: task 1
time 3: task 1
We’ve overshot task 1 by 1 minute, hence returning 1.
With the first three tasks, the optimal schedule can be:
time 1 : task 2
time 2 : task 1
time 3 : task 3
time 4 : task 1
time 5 : task 3
time 6 : task 3
Task 1 has a deadline 2, and it finishes at time 4. So it exceeds its deadline by 2.
Task 2 has a deadline 1, and it finishes at time 1. So it exceeds its deadline by 0.
Task 3 has a deadline 4, and it finishes at time 6. So it exceeds its deadline by 2.
Thus, the maximum time by which you overshoot a deadline is 2. No schedule can do better than this.
Similar calculation can be done for the case containing 5 tasks.
Limbajul de programare folosit: java8
Cod:
import java.io.*;
public class Solution {
static final int MAXD = 100000;
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do { c = read(); } while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') { sign = -1; c = read(); }
int val = 0;
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sign;
}
}
static class SegTree {
int n;
long[] mx;
long[] lazy;
SegTree(int n) {
this.n = n;
mx = new long[4 * n + 5];
lazy = new long[4 * n + 5];
build(1, 1, n);
}
void build(int node, int l, int r) {
if (l == r) {
mx[node] = -l;
return;
}
int mid = (l + r) >>> 1;
build(node << 1, l, mid);
build(node << 1 | 1, mid + 1, r);
mx[node] = Math.max(mx[node << 1], mx[node << 1 | 1]);
}
void apply(int node, long val) {
mx[node] += val;
lazy[node] += val;
}
void push(int node) {
long v = lazy[node];
if (v != 0) {
apply(node << 1, v);
apply(node << 1 | 1, v);
lazy[node] = 0;
}
}
void add(int ql, int qr, long val) {
add(1, 1, n, ql, qr, val);
}
void add(int node, int l, int r, int ql, int qr, long val) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
apply(node, val);
return;
}
push(node);
int mid = (l + r) >>> 1;
add(node << 1, l, mid, ql, qr, val);
add(node << 1 | 1, mid + 1, r, ql, qr, val);
mx[node] = Math.max(mx[node << 1], mx[node << 1 | 1]);
}
long max() {
return mx[1];
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int T = fs.nextInt();
SegTree st = new SegTree(MAXD);
StringBuilder out = new StringBuilder();
for (int i = 0; i < T; i++) {
int d = fs.nextInt();
int m = fs.nextInt();
st.add(d, MAXD, m);
long ans = st.max();
if (ans < 0) ans = 0;
out.append(ans).append('\n');
}
System.out.print(out);
}
}
Scor obtinut: 1.0
Submission ID: 464619834
Link challenge: https://www.hackerrank.com/challenges/task-scheduling/problem