Dyanmic Task Scheduling Interview Street

Question

The task scheduling problem for n tasks is solved by greedy algorithm. I have encountered this particular sort of problem in various coding challenges which asks to find out minimum of maximum overshoot dynamically. One of them is stated below:

Interview Street Problem:

You have a long list of tasks that you need to do today. Task i is specified by the deadline by which you have to complete it (Di) and the number of minutes it will take you to complete the task (Mi). 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 actually be possible complete all the tasks by their deadline, so you have decided to complete them so that the maximum amount by which a task's completion time overshoots its deadline is minimized.

My Approach

Now consider an intermediate stage where we have found the solution for i-1 tasks and have arranged them in sorted order. We have also stored the index of the task which had the maximum overshoot with i-1 tasks say maxLate. After the arrival of the *i*th task we check if D[i] < D[maxlate] then the new maxLate will be either old maxLate of the ith task. I am confused for the case when D[i] > D[maxlate]. Is a linear scan necessary for this case? Also suggest a good data structure for updating the new list and keeping them in sorted order. Thanks for your help.

Answer 1

class Schedule {

    int deadLine = 0;

    int taskCompletionTime = 0;

    int done = 0;

    Schedule(int deadline, int taskCompletionTime) {
        this.deadLine = deadline; 
        this.taskCompletionTime = taskCompletionTime;
    }
}

class TaskScheduler {

  public static void main(String args[]) {

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int max = 0;
    ArrayList<Schedule> sch = new ArrayList<Schedule>();
    for(int i = 0; i < n; i++) {
        int deadLine = in.nextInt();
        int taskCompletionTime = in.nextInt();
        Schedule s = new Schedule(deadLine, taskCompletionTime);
        int j = i-1;
        while(j >= 0 && sch.get(j).deadLine > s.deadLine) {
            Schedule s1 = sch.get(j);
            if(s1.deadLine <= s.deadLine) break;
            s1.done += s.taskCompletionTime;
            max = Math.max(max, s1.done - s1.deadLine);
            j--;
        }
        sch.add(j+1, s);
        if(j < 0)
            s.done = s.taskCompletionTime;
        else
            s.done = sch.get(j).done + s.taskCompletionTime;

        max = Math.max(max, s.done - s.deadLine);

        System.out.println(max);
     }
  }
}

Answer 2

First of all, you need to prove that given a set of task (m_i, d_i), the best schedule is finish the jobs according to their deadlines, i.e. emergent jobs first.

And the problem is equivalent to:

for each job in original order:
    dynamically insert this job (m_i, d_i) into a sorted job_list
    query max{ (sum(m_k for all k <= n) - d_n) for all n in job_list }

This algorithm run in O(N^2) where N is the number of jobs, which is too slow for getting accepted in interview street. However, we can use some advanced data structure, to speed up the insert and query operation.

I use a segment tree with lazy update to solve this problem in O(NlgN) time, and here's my code

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

class SegTree
{
public:
    SegTree(int left, int right, const vector<int>& original_data)
    {
        this->left = left;
        this->right = right;
        this->lazy_flag = 0;
        left_tree = right_tree = NULL;
        if (left == right)
        {
            this->value = this->max_value = original_data[left];
        }
        else
        {
            mid = (left + right) / 2;
            left_tree = new SegTree(left, mid, original_data);
            right_tree = new SegTree(mid + 1, right, original_data);
            push_up();
        }
    }
    void modify(int left, int right, int m_value)
    {
        if (this->left == left && this->right == right)
        {
            leaf_modify(m_value);
        }
        else
        {
            push_down();
            if (left <= mid)
            {
                if (right >= mid + 1)
                {
                    left_tree->modify(left, mid, m_value);
                    right_tree->modify(mid + 1, right, m_value);
                }
                else
                {
                    left_tree->modify(left, right, m_value);
                }
            }
            else
            {
                right_tree->modify(left, right, m_value);
            }
            push_up();
        }
    }
    int query(int left, int right)
    {
        if (this->left == left && this->right == right)
        {
            return this->max_value;
        }
        else
        {
            push_down();
            if (left <= mid)
            {
                if (right >= mid + 1)
                {
                    int max_value_l = left_tree->query(left, mid);
                    int max_value_r = right_tree->query(mid + 1, right);
                    return max(max_value_l, max_value_r);
                }
                else
                {
                    return left_tree->query(left, right);
                }
            }
            else
            {
                return right_tree->query(left, right);
            }
        }
    }
private:
    int left, right, mid;
    SegTree *left_tree, *right_tree;

    int value, lazy_flag, max_value;

    void push_up()
    {
        this->max_value = max(this->left_tree->max_value, this->right_tree->max_value);
    }
    void push_down()
    {
        if (this->lazy_flag > 0)
        {
            left_tree->leaf_modify(this->lazy_flag);
            right_tree->leaf_modify(this->lazy_flag);
            this->lazy_flag = 0;
        }
    }
    void leaf_modify(int m_value)
    {
        this->lazy_flag += m_value;
        this->max_value += m_value;
    }
};

vector<int> vec_d, vec_m, vec_idx, vec_rank, vec_d_reorder;

int cmp(int idx_x, int idx_y)
{
    return vec_d[idx_x] < vec_d[idx_y];
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++)
    {
        int d, m;
        scanf("%d%d", &d, &m);
        vec_d.push_back(d);
        vec_m.push_back(m);
        vec_idx.push_back(i);
    }

    sort(vec_idx.begin(), vec_idx.end(), cmp);
    vec_rank.assign(T, 0);
    vec_d_reorder.assign(T, 0);
    for (int i = 0; i < T; i++)
    {
        vec_rank[ vec_idx[i] ] = i;
    }
    for (int i = 0; i < T; i++)
    {
        vec_d_reorder[i] = -vec_d[ vec_idx[i] ];
    }

//  for (int i = 0; i < T; i++)
//  {
//      printf("m:%d\td:%d\tidx:%d\trank:%d\t-d:%d\n", vec_m[i], vec_d[i], vec_idx[i], vec_rank[i], vec_d_reorder[i]);
//  }

    SegTree tree(0, T-1, vec_d_reorder);

    for (int i = 0; i < T; i++)
    {
        tree.modify(vec_rank[i], T-1, vec_m[i]);
        int ans = tree.query(0, T-1);
        printf("%d\n", max(0,ans));
    }
}