aboutsummaryrefslogtreecommitdiff
path: root/single_threaded_cpu.rs
blob: 4defcb7dfbdeb2f76ca0991b5354bcd2fd08d278 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
use std::collections::BinaryHeap;
use std::cmp::Ordering;
struct Solution;
#[derive(PartialEq, Eq, Copy, Clone)]
struct Task {
    pub enqueue_time: i32,
    pub processing_time: i32,
    pub initial_idx: usize
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        if other.processing_time == self.processing_time {
            return Some(other.initial_idx.cmp(&self.initial_idx));
        }
        Some(other.processing_time.cmp(&self.processing_time))
    }
}

impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        if other.processing_time == self.processing_time {
            return other.initial_idx.cmp(&self.initial_idx);
        }
        other.processing_time.cmp(&self.processing_time)
    }
}

impl Solution {
    pub fn get_order(tasks: Vec<Vec<i32>>) -> Vec<i32> {
        let mut tasks = tasks.into_iter().enumerate().map(|(idx, task)| {
            Task {
                enqueue_time: task[0],
                processing_time: task[1],
                initial_idx: idx
            }
        }).collect::<Vec<Task>>();
        let (mut output, mut current_time) = (vec![], 0);
        let mut available_tasks: BinaryHeap<Task> = BinaryHeap::new();
        while tasks.len() > 0 || available_tasks.len() > 0 {
            while tasks.len() > 0 && tasks[tasks.len() - 1].enqueue_time <= current_time {
                let task = tasks.pop().unwrap();
                available_tasks.push(task);
            }
            if let Some(task) = available_tasks.pop() {
                output.push(task.initial_idx as i32);
                current_time += task.processing_time;
            } else {
                current_time = tasks[tasks.len() - 1].enqueue_time;
            }
        }
        output
    }
}

fn main() {
    let tasks = vec![vec![1,2],vec![2,4],vec![3,2],vec![4,1]];
    print!("{:?}", Solution::get_order(tasks));
}