Task Timing Problem (Java, C ++)

August 23, 2017 • ☕️ 5 min read • 🏷 computer, software

Translated by author into: English

Orjinali oku • View all translated posts

I want to share the problem that I had previously been asked in job interviews with software developers and the solution that I have developed.

Problem Definition

Dexter has a long list of jobs that you need to finish today. Dexter needs Mi minutes to finish any task and Di is the last finishing point of the task. No task can be completed longer than Di. But Dexter can complete a part of a task and pass it to another, and then he can return to that point.

But according to the job list, according to the given deadline, it seems impossible to complete all tasks. That’s why Dexter needs to try to finish tasks that exceed the deadline as soon as possible.

Input
The first line is the number of tasks (T). The values in the lines after T are Di and Mi, respectively.

Output
The optimal scheduled finishing time will include the maximum amount of duty that misses its finish date.

For better understanding, the following example can be examined:

Sample Input

Sample Output

Only the first task can be completed within 2 minutes and the timeout will not expire
With the first two tasks, an optimal timing can be:
Duration 1: Task 2
Duration 2: Task 1
Duration 3: Task 1
1st task printed on screen 1 (amount of exceeding Deadline) because it finished in 3 minutes, while it should finish in 2nd minute.
With the first three tasks an optimal timing can be:
Duration 1: Task 2
Duration 2: Task 1
Duration 3: Task 3
Duration 4: Task 1
Duration 5: Task 3
Duration 6: Task 3
Deadline of task 1 is 2 and it ends in 4 minutes. I mean, its deadline exceeds 2 minutes
The deadline for task 2 is 1 and it ends in 1 minute. So its deadline exceeds 0 minutes
Deadline of task 3 is 4 and it ends in 6 minutes. I mean, its deadline exceeds 2 minutes

So, I realize that Dexter has a deadline for a maximum of 2 minutes. It is not possible to make a better draft than this.

Similar calculations can be made for 5 tasks.

Problem Solution in Java

/*
 * Coded by hkucuk
 */
import java.util.*;
import java.io.*;

class SolutionSchedule{
    
	BufferedReader b_input;
	BufferedWriter b_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{
        
		b_input = new BufferedReader(new InputStreamReader(System.in));
		b_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);
			b_out.write(""+query(0,100000,0,0,100000));
			b_out.newLine();
		}
        
		b_out.flush();
	}

	int nextInt() throws IOException{        
		if(token == null || !token.hasMoreTokens())
			token = new StringTokenizer(b_input.readLine());
		return Integer.parseInt(token.nextToken());
	}

	Long nextLong() throws IOException{
		if(token == null || !token.hasMoreTokens())
			token = new StringTokenizer(b_input.readLine());
		return Long.parseLong(token.nextToken());
	}

	String next() throws IOException{
		if(token == null || !token.hasMoreTokens())
			token = new StringTokenizer(b_input.readLine());
		return token.nextToken();
	}

	public static void main(String[] args) throws Exception{
		new SolutionSchedule().solve();
	}
}

Problem Solution in C++

/*
 * Coded by hkucuk
 */
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

class SolutionSchedule{
    
    public:SolutionSchedule(int left, int right, const vector& 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 SolutionSchedule(left, mid, original_data);
            right_tree = new SolutionSchedule(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;
    SolutionSchedule *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 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] ];
    }

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