Task Scheduling : Challenge | Search | Algorithms | HackerRank

Task Scheduling : Challenge | Search | Algorithms | HackerRank
You have a long list of tasks that you need to do today. To accomplish task i you need Mi minutes, and the deadline for this task is Di. 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.
http://ganlu.name/blog/archives/hackerrank-task-scheduling

Statement: if  and  finished after , the max overshoot might be less than that when  finished before 

The basic solution is to just sort the list and do the calculation, however, what they ask is not just one final answer, but  answers with dynamically increasing set of tasks, this turns the problem into an interval query’n’update problem, what my solution is:

Sort the whole set of tasks first, and each of them have its rank, given the order of input, put the tasks input the spot according to its rank , then the answer would be:

where 

https://github.com/ningke/tasksched
https://e2718281828459045.wordpress.com/category/programming/hackerrank/

https://codepair.hackerrank.com/paper/N0EOdIbT?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
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();
}
Read full article from Task Scheduling : Challenge | Search | Algorithms | HackerRank