aboutsummaryrefslogtreecommitdiff
path: root/single_threaded_cpu.rs
diff options
context:
space:
mode:
Diffstat (limited to 'single_threaded_cpu.rs')
-rw-r--r--single_threaded_cpu.rs59
1 files changed, 59 insertions, 0 deletions
diff --git a/single_threaded_cpu.rs b/single_threaded_cpu.rs
new file mode 100644
index 0000000..4defcb7
--- /dev/null
+++ b/single_threaded_cpu.rs
@@ -0,0 +1,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));
+}