Table of Contents
Task Scheduling – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Task Scheduling HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define NMAX 300000
#define NN 100000
#define INF 1000000000LL
using namespace std;
typedef long long LL;
struct N{//data to store in tree
LL each,maxsub; //operation load.log update.,subtree statistic(calculate sub tree status in every update)
N(){
each = 0;
maxsub = -INF;
}
};
N st[NMAX];
void update2(int ni,int s,int e,int ps,int pe,LL v){
if(ps > pe)return;
if(pe < s || ps > e)return;
else if(ps <= s && pe >= e){//update all
st[ni].each += v;
}
else{
int mid = (s+e)/2;
update2(ni*2+1,s,mid,ps,min(mid,pe),v);
update2(ni*2+2,mid+1,e,max(mid+1,ps),pe,v);
LL sub1 = st[ni*2+1].each;
LL sub2 = st[ni*2+2].each;
if(mid>s)sub1 += st[ni*2+1].maxsub;
if(mid+1<e)sub2 += st[ni*2+2].maxsub;
st[ni].maxsub = max(sub1,sub2);
}
}
LL query2(int ni,int s,int e,int ps,int pe){
if(ps > pe)return -INF;
if(pe < s || ps > e)return -INF;
else if(ps <= s && pe >= e){//get all segment
if(s==e)return st[ni].each;
else return st[ni].maxsub + st[ni].each;
}
else{
int mid = (s+e)/2;
return max(query2(2*ni+1,s,mid,ps,min(pe,mid)),query2(2*ni+2,mid+1,e,max(ps,mid+1),pe))+st[ni].each;
}
}
int main(){
for(LL i=0;i<=NN;i++){
update2(0,0,NN,i,i,-i);
}
int nn;scanf("%d",&nn);
for(int i=0;i<nn;i++){
int a,b;scanf("%d%d",&a,&b);
update2(0,0,NN,a,NN,b);
LL ret = max(0LL,query2(0,0,NN,0,NN));
printf("%lld\n",ret);
}
return 0;
}
Java Task Scheduling HackerRank Solution
import java.util.*;
import java.io.*;
class Solution
{
BufferedReader input;
BufferedWriter out;
StringTokenizer token;
int[] ST;
int[] add;
void update(int s,int e,int x,int a,int b,int v)
{
if(s > b || e < a)return;
if(s >= a && e <= b)
{
add[x] += v;
return;
}
add[2*x+1] += add[x];
add[2*x+2] += add[x];
add[x] = 0;
update(s,(s+e)/2,2*x+1,a,b,v);
update((s+e)/2+1,e,2*x+2,a,b,v);
ST[x] = Math.max(ST[2*x+1]+add[2*x+1],ST[2*x+2]+add[2*x+2]);
}
void build(int s,int e,int x)
{
if(s==e)
{
ST[x] = -s;
return;
}
build(s,(s+e)/2,2*x+1);
build((s+e)/2+1,e,2*x+2);
ST[x] = Math.max(ST[2*x+1],ST[2*x+2]);
}
int query(int s,int e,int x,int a,int b)
{
if(s > b || e < a)return 0;
if(s >= a && e <= b)
{
return ST[x]+add[x];
}
add[2*x+1] += add[x];
add[2*x+2] += add[x];
add[x] = 0;
ST[x] = Math.max(ST[2*x+1]+add[2*x+1],ST[2*x+2]+add[2*x+2]);
int first = query(s,(s+e)/2,2*x+1,a,b);
int second = query((s+e)/2+1,e,2*x+2,a,b);
return Math.max(first,second);
}
void solve() throws IOException
{
input = new BufferedReader(new InputStreamReader(System.in));
out = new BufferedWriter(new OutputStreamWriter(System.out));
int T = nextInt();
int maxD = 4*(100000+3);
ST = new int[maxD];
add = new int[maxD];
build(0,100000,0);
for(int t = 0; t < T; t++)
{
int D = nextInt();
int M = nextInt();
update(0,100000,0,D,100000,M);
out.write(""+query(0,100000,0,0,100000));
out.newLine();
}
out.flush();
}
int nextInt() throws IOException
{
if(token == null || !token.hasMoreTokens())
token = new StringTokenizer(input.readLine());
return Integer.parseInt(token.nextToken());
}
Long nextLong() throws IOException
{
if(token == null || !token.hasMoreTokens())
token = new StringTokenizer(input.readLine());
return Long.parseLong(token.nextToken());
}
String next() throws IOException
{
if(token == null || !token.hasMoreTokens())
token = new StringTokenizer(input.readLine());
return token.nextToken();
}
public static void main(String[] args) throws Exception
{
new Solution().solve();
}
}
Python 3 Task Scheduling HackerRank Solution
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)
Python 2 Task Scheduling HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
class Arbre :
"arbre"
def inserer(T, e) :
if T.vide :
# print "On met dans le vide"
T.vide = False
T.deadline = e[0]
#T.temps = e[1]
T.ajoutdroite = e[1]
T.retard = e[1]-e[0]
T.droite = False
T.gauche = False
#T.filsdroite = Arbre()
#T.filsdroite.vide = True
#T.filsgauche = Arbre()
#T.filsgauche.vide = True
#T.filsgauche.retard=0
else :
if e[0] == T.deadline :
# print "On combine"
#T.temps += e[1]
T.ajoutdroite += e[1]
if (T.droite and T.gauche) :
T.retard = max(T.filsgauche.retard, T.ajoutdroite-T.deadline,T.ajoutdroite + T.filsdroite.retard)
elif T.droite :
T.retard = max(T.ajoutdroite-T.deadline, T.ajoutdroite + T.filsdroite.retard)
elif T.gauche :
T.retard = max(T.filsgauche.retard, T.ajoutdroite-T.deadline)
else :
T.retard += e[1]
elif e[0] < T.deadline :
# print "On insere a gauche"
T.ajoutdroite += e[1]
if T.gauche :
inserer(T.filsgauche, e)
else :
T.filsgauche = Arbre()
T.filsgauche.vide = True
T.gauche = True
inserer(T.filsgauche, e)
if T.droite :
T.retard = max(T.filsgauche.retard, T.ajoutdroite-T.deadline,T.ajoutdroite + T.filsdroite.retard)
else :
T.retard = max(T.filsgauche.retard, T.ajoutdroite-T.deadline)
else :
# print "On insere a droite"
if T.droite :
inserer(T.filsdroite, e)
else :
T.filsdroite = Arbre()
T.filsdroite.vide = True
T.droite = True
inserer(T.filsdroite, e)
if T.gauche :
T.retard = max(T.filsgauche.retard, T.ajoutdroite-T.deadline,T.ajoutdroite + T.filsdroite.retard)
else :
T.retard = max(T.ajoutdroite-T.deadline, T.ajoutdroite + T.filsdroite.retard)
# print T.retard
T = Arbre()
T.vide = True
Temps = map(eval, raw_input().split())
#Li = []
#for i in range(Temps[0]) :
# D, M = map(eval, raw_input().split())
# Li += [[D,M]]
#Temps = [10]
#print Temps
#import random
#Li =[]
#for j in range(Temps[0]) :
# r = random.randint(1,10000)
# r=100
# Li += [[r,random.randint(1,min(r,1000))]]
i=0
while i <Temps[0]:
D, M = map(eval, raw_input().split())
inserer(T, [D,M])
#inserer(T, Li[i])
#print Li[i]
print max(0,T.retard)
i+=1
#print "fini"
C Task Scheduling HackerRank Solution
#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("%d\n", tree->max_over >= 0 ? tree->max_over : 0);
}
free_task(tree, 1);
return 0;
}
Leave a comment below
