Algorithm
Problem Name: beecrowd | 2823
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2823
Eearliest Deadline First
By Emilio Wuerges, UFFS Brazil
Timelimit: 1
Your job for this problem is to check if it is possible to schedule a set of periodic tasks under real-time constraints.
A real-time task is defined by two numbers. The first number is the computational cost of the task. It is the computational cost of each complete run of the task. The second number is the period of the process. In other words, the process restarts again after each period.
The task set will be scheduled using the EDF algorithm (Earliest Deadline First). It is known that EDF is optimal. This means that if a set of tasks cannot be scheduled by EDF, there isn't another algorithm that can schedule it.
The operating system that will run these tasks runs on a single core machine. The tasks are preemptable. That is, a task can take the place of another task during its run, if required.
Consider that the cost of switching tasks is 0.
Input
The first line of the input has a value
, which states the number of processes under schedule.
Every N following line represents a process, and has 2 values
and
, that represent the computational cost and the period of each process, respectively.
Output
The output consists of a single line, with the string OK or the string FAIL, if the scheduling is possible or not, respectively.
Input Samples | Output Samples |
2 |
OK |
4 |
FAIL |
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("node:fs")
const [[N], ...input] = readFileSync("/dev/stdin", "utf8")
.split("\n", 10 + 1)
.map((line) => line.split(" ", 2).map(value => Number.parseInt(value, 10)))
console.log(
input.splice(0, N).reduce((total, [C, P]) => total + (C / P), 0) <= 1
? "OK"
: "FAIL"
)
Copy The Code &
Try With Live Editor
Input