In this HackerRank Task Scheduling problem solution, you have a long list of tasks that you need to do today. To accomplish the task you need M minutes, and the deadline for this task is D. 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.
Problem solution in Python.
def returnIndex(array,number):
if not array:
return None
if len(array) == 1:
if number > array[0]:
return 0
else:
return None
si = 0
ei = len(array)-1
return binarySearch(array,number,si,ei)
def binarySearch(array,number,si,ei):
if si==ei:
if number >= array[si]:
return si
else:
return si-1
else:
middle = (ei-si)//2 +si
if number > array[middle]:
return binarySearch(array,number,middle+1,ei)
elif number < array[middle]:
return binarySearch(array,number,si,middle)
else:
return middle
def addJob(length, array, deadline,minutes,late):
if length < deadline:
for i in range(deadline-length):
array.append(i+length)
length = deadline
minLeft = minutes
index = returnIndex(array,deadline-1)
if index != None:
while index >=0 and minLeft >0:
array.pop(index)
index -= 1
minLeft -=1
while minLeft >0 and array and array[0] < deadline:
array.pop(0)
minLeft -=1
late += minLeft
return late,length
if __name__ == '__main__':
n = int(input().strip())
time = 0
length = 0
nl = []
late = 0
for op in range(n):
job = input().split(' ')
late,length = addJob(length,nl,int(job[0]),int(job[1]),late)
print(late)
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
class Task implements Comparable<Task> {
public long D;
public long M;
public Task(long D, long M) {
this.D = D;
this.M = M;
}
public int compareTo(Task task) {
if (this.D < task.D) {
return -1;
} else if (this.D > task.D) {
return 1;
} else {
return 0;
}
}
}
public class Solution {
/*
* Complete the solve function below.
*/
public static Map<Long, Long> map = new HashMap<Long, Long>();
public static long maxSoFar = -1;
public static long deadlineOfMax = -1;
static long solve(List<Long> tasks, long D, long M, int upIndex) {
/*
* Write your code here.
*/
if (maxSoFar >= 0 && D <= deadlineOfMax) {
map.put(deadlineOfMax, map.get(deadlineOfMax) + M);
maxSoFar += M;
return Math.max(0, maxSoFar);
}
if (!map.containsKey(D)) {
map.put(D, M);
} else {
map.put(D, map.get(D) + M);
}
if (tasks.size() == 0) {
tasks.add(D);
return Math.max(0, M - D);
} else {
long total = 0;
int index = 0;
long max = -1;
boolean found = false;
while (index < tasks.size() &&
tasks.get(index) <= D) {
if (tasks.get(index) == D)
found = true;
total += map.get(tasks.get(index));
long diff = total - tasks.get(index);
if (diff > max) {
max = diff;
maxSoFar = max;
deadlineOfMax = tasks.get(index);
}
index++;
}
if (!found)
tasks.add(index, D); // linear, can we avoid this?
while (index < tasks.size()) {
total += map.get(tasks.get(index));
long diff = total - tasks.get(index);
if (diff > max) {
max = diff;
maxSoFar = max;
deadlineOfMax = tasks.get(index);
}
index++;
}
return Math.max(0, max);
}
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(scanner.nextLine().trim());
List<Long> tasks = new ArrayList<Long>(t);
for (int tItr = 0; tItr < t; tItr++) {
String[] dm = scanner.nextLine().split(" ");
int d = Integer.parseInt(dm[0].trim());
int m = Integer.parseInt(dm[1].trim());
long result = solve(tasks,d, m, tItr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
}
}
Problem solution in C++.
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int BufferSize = 120000;
struct Node
{
int from;
int to;
long long maximum;
long long offset;
Node *left;
Node *right;
};
int len = 0;
Node nodes[BufferSize*2];
int d[BufferSize];
int m[BufferSize];
int t;
Node *MakeTree(int from, int to)
{
Node *p = &nodes[len++];
p->from = from;
p->to = to;
p->maximum = -(1LL << 60);
p->offset = 0;
if (from+1 < to)
{
int mid = (from + to)/2;
p->left = MakeTree(from, mid);
p->right = MakeTree(mid, to);
}
return p;
}
void Insert(Node *p, int from, int to, long long x)
{
if (from <= p->from && p->to <= to)
{
//x += p->offset;
if (x > p->maximum)
p->maximum = x;
}
else
{
int mid = (p->from + p->to)/2;
if (from < mid && to > p->from)
{
Insert(p->left, from, to, x);
long long tmp = p->left->maximum + p->left->offset;
if (tmp > p->maximum)
p->maximum = tmp;
}
if (from < p->to && to > mid)
{
Insert(p->right, from, to, x);
long long tmp = p->right->maximum + p->right->offset;
if (tmp > p->maximum)
p->maximum = tmp;
}
}
}
void Add(Node *p, int from, int to, long long x)
{
if (from <= p->from && p->to <= to)
{
p->offset += x;
}
else
{
int mid = (p->from + p->to)/2;
if (from < mid && to > p->from)
{
Add(p->left, from, to, x);
long long tmp = p->left->maximum + p->left->offset;
if (tmp > p->maximum)
p->maximum = tmp;
}
if (from < p->to && to > mid)
{
Add(p->right, from, to, x);
long long tmp = p->right->maximum + p->right->offset;
if (tmp > p->maximum)
p->maximum = tmp;
}
}
}
int main(int argc, char *argv[])
{
scanf("%d", &t);
for (int i = 0; i < t; ++i)
scanf("%d %d", &d[i], &m[i]);
int max_d = *max_element(d, d + t) + 1;
MakeTree(0, max_d);
for (int i = 0; i < t; ++i)
{
Add(nodes, d[i], max_d, m[i]);
Insert(nodes, d[i], d[i]+1, -d[i]);
cout << max(0LL, nodes->maximum) << endl;
}
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <stdlib.h>
struct task {
int l_cost, cost, r_cost, total_cost;
int time, max_over;
struct task *l, *r;
};
void update_task(struct task *t) {
int cur_over, max_over;
max_over = t->cost - t->time;
if (t->l) {
t->l_cost = t->l->total_cost;
max_over += t->l_cost;
cur_over = t->l->max_over;
if (cur_over > max_over) max_over = cur_over;
} else {
t->l_cost = 0;
}
if (t->r) {
t->r_cost = t->r->total_cost;
cur_over = t->r->max_over + t->l_cost + t->cost;
if (cur_over > max_over) max_over = cur_over;
} else {
t->r_cost = 0;
}
t->total_cost = t->l_cost + t->cost + t->r_cost;
t->max_over = max_over;
}
struct task *new_task(int time, int cost) {
struct task *t;
t = malloc(sizeof(struct task));
t->l = t->r = 0;
t->time = time;
t->cost = cost;
update_task(t);
return t;
}
void free_task(struct task *t, int recur) {
if (t) {
if (recur) {
free_task(t->l, recur);
free_task(t->r, recur);
}
free(t);
}
}
void insert_task(struct task **tree, struct task *t) {
struct task *cur_task, **next_tree;
if (cur_task = *tree) {
next_tree = (t->time < cur_task->time) ? &(cur_task->l) : &(cur_task->r);
insert_task(next_tree, t);
update_task(cur_task);
} else {
*tree = t;
}
}
int main(void) {
int i, num_tasks, task_due, task_minutes;
struct task *tree = 0;
scanf("%d", &num_tasks);
for (i = 0; i < num_tasks; ++i) {
scanf("%d %d", &task_due, &task_minutes);
insert_task(&tree, new_task(task_due, task_minutes));
printf("%dn", tree->max_over >= 0 ? tree->max_over : 0);
}
free_task(tree, 1);
return 0;
}