hkucuk

Görev Zamanlaması Problemi (Java, C++)

23 Ağustos 2017 • ☕️ 5 dk okuma • 🏷 bilgisayar, yazılım

Yazar tarafından şu dillere çevrildi: English


Daha önce yazılımcılara iş mülakatlarında sorulmuş bir problem ve bu probleme benim geliştirdiğim çözümü paylaşmak istiyorum.

Problem Tanımlaması

Dexter’ın elinde bugün yapıp bitirmesi gerek uzun bir iş listesi vardır. Dexter’ın herhangi bir i görevini bitirebilmesi için Mi dakikaya ihtiyacı vardır ve i görevinin son bitirme anı Di’dir. Hiçbir görev Di’den daha uzun sürede bitirilemez. Fakat Dexter bir görevin bir parçasını tamamlayıp başka bir göreve geçebilir ve ardından o göreve geri dönebilir.

Fakat iş listesine bakıldığında verilen deadline’a göre tüm görevlerin tamamlanması mümkün gibi gözükmüyor. Bu yüzden Dexter’ın deadline’ını aşan görevleri olabildiğince kısa sürelerde bitirmeye çalışması gerekiyor.

Girdi
İlk girilen satır görevlerin sayısı (T). T’den sonra girilen satırlardaki değerler ise sırasıyla Di ve Mi.

Çıktı
Optimal planlanan bitirme süresi, kendi bitiş tarihini ıskalayan azami görev miktarını içerecektir.

Daha iyi anlaşılması için aşağıdaki örnek incelenebilir:

Örnek Girdi

5
2 2
1 1
4 3
10 1
2 1

Örnek Çıktı

0
1
2
2
3
  • Yanlızca ilk görev 2 dakika içerisinde tamamlanabilir ve süre aşımı olmaz
  • İlk iki görev ile şöyle bir optimal zamanlama yapılabilir:
    Süre 1: Görev 2
    Süre 2: Görev 1
    Süre 3: Görev 1
    1. görev 2. dakikada bitmesi gerekirken 3. dakikada bittiği için ekrana 1 yazdırdık (Deadline’ı aşma miktarı).
  • İlk üç görev ile şöyle bir optimal zamanlama yapılabilir:
    Süre 1: Görev 2
    Süre 2: Görev 1
    Süre 3: Görev 3
    Süre 4: Görev 1
    Süre 5: Görev 3
    Süre 6: Görev 3
  • Görev 1’in deadline’ı 2 ve o 4. dakikada bitiyor. Yani kendi deadline’ını 2 dakika aşıyor
  • Görev 2’in deadline’ı 1 ve o 1. dakikada bitiyor. Yani kendi deadline’ını 0 dakika aşıyor
  • Görev 3’in deadline’ı 4 ve o 6. dakikada bitiyor. Yani kendi deadline’ını 2 dakika aşıyor

Böylece Dexter’ın deadline’ı maksimum 2 dakika aştığını anlamış olduk. Bundan daha iyi bir taslak yapmak olası değildir.

Benzer hesaplama 5 görev için de yapılabilir.

Java’da Problemin Çözümü

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

C++‘da Problemin Çözümü

/*
 * 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));
    }
}