HackerRank Task Scheduling Problem Solution

In this post, we will solve HackerRank Task Scheduling Problem Solution.

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.
Input Format
The first line contains the number of tasks, T. Each of the next T lines contains two integers,
Di and Mi.

Output Format

Output T lines. The i 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

Sample Output

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.

HackerRank Task Scheduling Problem Solution

Task Scheduling C Solution

#include<stdio.h>
#include<stdlib.h>
#define MAXN 100010
#define max(a,b) a > b? a : b
typedef struct node
{
    int begin;
    int end;
    struct node* left;
    struct node* right;
    int sum;
    int over;
}NODE;
typedef NODE* PNODE;
PNODE root;
int deadline, time;
PNODE create_tree(int begin, int end)
{
    PNODE t = (PNODE)malloc(sizeof(NODE));
    t->begin = begin;
    t->end = end;
    t->sum = 0;
    t->over = -MAXN * 1000;
    if(begin == end)  {
        t->left = t->right = NULL;
        return t;
    }
    int mid = (begin + end) / 2;
    t->left = create_tree(begin, mid);
    t->right = create_tree(mid + 1, end);
    return t;
}
void update_tree(PNODE t)
{
    if(t->end == t->begin) {
        t->sum += time;
        t->over = t->sum - deadline;
    }
    else {
        int mid = (t->begin + t->end) >> 1;
        if(deadline <= mid) {
            update_tree(t->left);
        }
        else {
            update_tree(t->right);
        }
        t->sum = t->left->sum + t->right->sum;
        t->over = max(t->left->over, t->right->over + t->left->sum);
    }
}
int main()
{
    root = create_tree(1, MAXN);
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &deadline, &time);
        update_tree(root);
        printf("%d\n", root->over > 0? root->over: 0);
    }
}

Task Scheduling C++ Solution

#include <bits/stdc++.h>
using namespace std;

int l2_ceil(int x) {
    assert(x > 0);
    int r = (x & (x-1)) != 0;
    while (x >>= 1) ++r;
    return r;
}

struct node {
    int v, s, e, lazy;
};

using tree = vector<node>;

int mk_node(vector<node>& t, const vector<int>& l, int s, int e, int n) {
    if (s == e) {
        return (t[n] = {l[s], s, s, 0}).v;
    }

    int m = (s + e) / 2;
    return (t[n] = {max(mk_node(t, l, s, m, 2*n), mk_node(t, l, m+1, e, 2*n+1)), s, e}).v;
}

tree mk_tree(const vector<int>& l) {
    vector<node> r(1 << (l2_ceil(l.size()) + 1));
    mk_node(r, l, 0, l.size() - 1, 1);
    return r;
}

void add_node(vector<node>& t, int s, int e, int x, int k) {
    auto& n = t[k];
    if (s <= n.s && n.e <= e) {
        n.lazy += x;
        return;
    }
    if (n.e < s || e < n.s) return;

    add_node(t, s, e, x, 2*k);
    add_node(t, s, e, x, 2*k+1);
    n.v = max(t[2*k].v + t[2*k].lazy, t[2*k+1].v + t[2*k+1].lazy);
}

int query_node(vector<node>& t, int s, int e, int k) {
    auto& n = t[k];
    if (s <= n.s && n.e <= e) return n.v + n.lazy;
    if (n.e < s || e < n.s) return numeric_limits<int>::min();

    if (n.lazy) {
        n.v += n.lazy;
        add_node(t, n.s, n.e, n.lazy, 2*k);
        add_node(t, n.s, n.e, n.lazy, 2*k+1);
        n.lazy = 0;
    }
    return max(query_node(t, s, e, 2*k), query_node(t, s, e, 2*k+1));
}

int query(tree& t, int s, int e) {
    return query_node(t, s, e, 1);
}

void add(tree& t, int i, int x) {
    add_node(t, i, i, x, 1);
}

void add_range(tree& t, int s, int e, int x) {
    add_node(t, s, e, x, 1);
}

struct task {
    int d, m, i;
};

int main() {
    int T; cin >> T;
    vector<task> ts;
    for (int i = 0; i < T; ++i) {
        task t{0,0,i};
        cin >> t.d >> t.m;
        ts.push_back(t);
    }
    sort(begin(ts), end(ts), [](auto& t1, auto& t2) { return t1.d < t2.d; });
    vector<int> ixs(T);
    for (int i = 0; i < T; ++i) {
        ixs[ts[i].i] = i;
    }
    vector<int> over(T);
    for (int i = 0; i < T; ++i) {
        over[i] = -ts[i].d;
    }
    auto tr = mk_tree(over);
    for (int i = 0; i < T; ++i) {
        auto j = ixs[i];
        auto t = ts[j];
        add_range(tr, j, T-1, t.m);
        cout << max(0, query(tr, 0, T-1)) << endl;
    }
}

Task Scheduling C Sharp Solution

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

public class Solution {
	private class Slot {
		public int Time { get; set; }
		public int Task { get; set; }
		public int Difference { get; set; }

		public Slot(int task, int time, int diff) {
			this.Time = time;
			this.Task = task;
			this.Difference = diff;
		}

		public override string ToString() {
			return string.Format("{0}: Task #{1}, {2} minutes over", Time, Task, Difference);
		}
	}

	private int max = 0;
	private LinkedList<Slot> slots = new LinkedList<Slot>();
	private LinkedListNode<Slot> maxNode = null;
	//private long count = 0;

	private void ParseLine(string ln, out int D, out int M) {
		string[] parts = ln.Split(' ');
		D = int.Parse(parts[0]);
		M = int.Parse(parts[1]);
	}

	private void Clean() {
		// any slots before max slot can be removed
		LinkedListNode<Slot> first = slots.First;
		LinkedListNode<Slot> node = maxNode.Previous;

		while (node != null && node != first) {
			LinkedListNode<Slot> lastNode = node.Previous;
			slots.Remove(node);
			node = lastNode;
		}
	}

	private void PostProcess(LinkedListNode<Slot> slotNode, int diff, int T, int M) {
		Slot slot = slotNode.Value;
		LinkedListNode<Slot> newNode = new LinkedListNode<Slot>(new Slot(T, slot.Time + M, diff));
		slots.AddAfter(slotNode, newNode);
		if (diff > max) {
			max = diff;
			maxNode = newNode;
		}
	}

	private int FindMax(int T, int D, int M) {

		LinkedListNode<Slot> slotNode = slots.Last;

		for (; ; ) {
			LinkedListNode<Slot> lastSlotNode = slotNode.Previous;
			Slot slot = slotNode.Value;
			int diffOfStay = slot.Time + M - D;

			if (lastSlotNode == null) {
				// on first slot
				PostProcess(slotNode, diffOfStay, T, M);
				break;
			}

			Slot lastSlot = lastSlotNode.Value;
			int diffOfMoveUp = lastSlot.Time + M - D;
			int maxOfMoveUp = Math.Max(diffOfMoveUp, slot.Difference + M);
			int maxOfStay = Math.Max(diffOfStay, slot.Difference);

			if (maxOfMoveUp < maxOfStay) {
				// we need to move up current minute task
				slot.Difference += M;
				slot.Time += M;
				if (slot.Difference > max) {
					max = slot.Difference;
					maxNode = slotNode;
				}
				slotNode = lastSlotNode;
			} else {
				PostProcess(slotNode, diffOfStay, T, M);
				break;
			}
		}

		Clean();
		return max;
	}

	private void Print() {
		foreach (var slot in slots) {
			Console.WriteLine(slot);
		}
	}

	private void Run(TextReader rd) {
		int T = int.Parse(rd.ReadLine());
		int D, M;

		slots.AddFirst(new Slot(0, 0, 0));
		maxNode = slots.First;

		for (int i = 1; i <= T; i++) {
			ParseLine(rd.ReadLine(), out D, out M);
			Console.WriteLine(FindMax(i, D, M));
		}
		//Console.WriteLine(count);
		//Print();
		//Console.ReadKey();
	}

	public static void Main(string[] args) {
		TextReader rd = Console.In;
		if (args.Length != 0) rd = new StreamReader(new FileStream(args[0], FileMode.Open, FileAccess.Read));
		new Solution().Run(rd);
	}

}

Task Scheduling Java Solution

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

Task Scheduling JavaScript Solution

function processData(input) {
    input = input.trim().split('\n');
    var N = Number(input.shift())
    var arr = new Array(input.length)

    for (var i = 0; i < input.length; i++) {
        var d = Number(input[i].substr(0, input[i].indexOf(' ')))
        var m = Number(input[i].substr(input[i].indexOf(' ') + 1))
        arr[i] = { d: d, m: m };
    }

    var step = 0;
    var ans = 0;
    var used = [];

    for (var i = 0; i < arr.length; i++) {
        step += arr[i].m;
        arr[i].pos = step;
        used.push(arr[i]);

        for (var j = i - 1; j >= 0; j--) {
            var diff = used[j + 1].pos - used[j + 1].d
            var comp = used[j].pos - used[j].d + used[j + 1].m

            if (diff > 0 && comp > 0 && diff < ans && i > 1000) {
                break
            }

            if (diff > comp) {
                used[j + 1].pos -= used[j].m;
                used[j].pos += used[j + 1].m;
                var tmp = used[j + 1]
                used[j + 1] = used[j]
                used[j] = tmp
                ans = Math.max(ans, comp)
            } else {
                break;
            }
        }

        ans = Math.max(ans, arr[i].pos - arr[i].d)
        console.log(ans)
    }
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
    processData(_input);
});

Task Scheduling Python Solution

import sys
class tree:
    __slots__ = ("left", "right", "free", "size")
    def __init__(self, size = 2):
        if size == 0:
            return None
        if size > 1:
            half = size // 2
            self.left = tree(size - half)
            self.right = tree(half)
        else:
            self.left = self.right = None
        self.free = size
        self.size = size

    def resize(self, n):
        while self.size < n:
            t = tree(0)
            t.left = self
            t.right = tree(self.size)
            t.free = t.left.size + t.right.size
            t.size = self.size * 2
            self = t
        return self

    def recfill(self, dur, end):
        if dur == 0:
            return 0
        if self.free == 0:
            return 0 
        if (self.size <= dur and dur <= end) or self.size == 1:
            r = self.free
            self.free = 0
            return r
        r = 0
        if self.left.size < end:
            r += self.right.recfill(dur, end - self.left.size)
        r += self.left.recfill(dur - r, end)
        self.free -= r
        return r

t = tree()
r = 0
nlines = int(sys.stdin.readline().strip())
for i in range(nlines):
    two_strings = sys.stdin.readline().strip().split(" ")
    end, dur = (int(i) for i in two_strings)
    t = t.resize(end)
    b = t.recfill(dur, end)
    r = r + dur - b
    print(r)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python