# HackerRank Task Scheduling problem solution

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

array.append(i+length)
minLeft = minutes
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(' ')
print(late)
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public long D;
public long M;

public Task(long D, long M) {
this.D = D;
this.M = M;
}

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) {
/*
*/
if (maxSoFar >= 0 && D <= deadlineOfMax) {
maxSoFar += M;
return Math.max(0, maxSoFar);
}

if (!map.containsKey(D)) {
map.put(D, M);
} else {
map.put(D, map.get(D) + M);
}

return Math.max(0, M - D);
} else {
long total = 0;
int index = 0;
long max = -1;
boolean found = false;
found = true;
long diff = total - tasks.get(index);
if (diff > max) {
max = diff;
maxSoFar = max;
}
index++;
}
if (!found)
long diff = total - tasks.get(index);
if (diff > max) {
max = diff;
maxSoFar = max;
}
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());
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();
}
}
```

{"mode":"full","isActive":false}

## 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)
{
long long tmp = p->left->maximum + p->left->offset;
if (tmp > p->maximum)
p->maximum = tmp;
}
if (from < p->to && to > mid)
{
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)
{
Insert(nodes, d[i], d[i]+1, -d[i]);
cout << max(0LL, nodes->maximum) << endl;
}

return 0;
}```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>

int l_cost, cost, r_cost, total_cost;
int time, max_over;
};

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;
}

t->l = t->r = 0;
t->time = time;
t->cost = cost;
return t;
}

if (t) {
if (recur) {
}
free(t);
}
}

} else {
*tree = t;
}
}

int main(void) {
for (i = 0; i < num_tasks; ++i) {