Question:
A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes. The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.
Solution:
public int solution(int X, int[] A) { boolean[] tiles = new boolean[X]; int todo = X; for (int i = 0; i < A.length; i++) { int internalIndex = A[i] - 1; if (!tiles[internalIndex]) { todo--; tiles[internalIndex] = true; } if (todo == 0) return i; } return -1; }
This algorithm only requires O(n)
time, since it always keeps track of how many "holes" we still have to fill with leaves.
todo
is the number of leaves still required to build the "bridge" of leaves. Whenever a leaf falls down, we first check whether there not already is a leaf at the position it falls down. If not, we decrement todo
, fill the hole and go on. As soon as todo
reaches 0
, the entire river is covered ;)
相关推荐
Earliest-deadline-first (EDF) is good for scheduling real-time tasks in order to meet timing constraint. Earliest-deadline-first (EDF) is real-time disk-scheduling algorithms that service realtime ...
2 实现EDF(Earliest-Deadline-First)实时调度算法 EDF deadline越近的进程越先执行 实时调度 设置进程的优先级,保证进程的优先级高于其他用户进程,以保证它的实时性。但要考虑不会影响系统进程的执行。
Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project. Input Specification: Each input file contains one test case. Each case ...
首先, 提出反向异构最早完成时间优先( heterogeneous earliest finish time,HEFH) 调度策略,可以快速求出多个工作流中每个子任务的近似最晚开始时间和子期限,并基于最晚开始时间定义了当前任务相对宽松度的衡量...
将要处理的文件(输入文件)粘贴到 Earliest-Priority-Selector 文件夹中。 打开“EARLIEST PRIORITY SELECTOR.py”。 在指示的字段中写入输入文件名。 添加文件扩展名(.txt)是必不可少的,
This book covers concepts such as the differences between Just-In-Time (JIT) and Ahead-Of-Time (AOT) compilation in Angular, alongside NgModules, components and directives. It also goes into detail on...
基于earliest调度策略对带驻留时间约束单臂组合设备的暂态分析.pdf
操作系统课程设计报告 在Minix系统中添加一个系统调用 实现实时进程 使用彩票调度算法
给出了改进的FTT(Flexible Time-Triggered communication paradigm)网络调度模型,提出了新的周期性实时消息链路可调度性优化判定方法,在此基础上设计了一种基于EDF(Earliest Deadline First)的实时调度算法。...
sbt clone git@github.com:navicore/ehtail.gitcd ehtail./install.sh <open>用法求助ehtail -h用于从带有8个分区的eh开头读取所有消息ehtail -c myConsumerGroup -o EARLIEST -p 8 "Endpoint=sb://CHANGEME.service...
Creating a World Without Poverty tells the stories of some of the earliest examples of social businesses, including Yunus's own Grameen Bank. It reveals the next phase in a hopeful economic and social...
unique feature that they do not need a time varying input to produce a time varying output. The periodicity and amplitude of the produced oscillation are regulated by the system’s energy balance ...
A reliability study of earliest school recollections Psychology in the Schools Volume 24, October I987 A RELIABILITY STUDY OF EARLIEST SCHOOL RECOLLECTIONS HENRY J . ROTH Duke University To ...
$ ltap 'instrumentation app=api earliest=-1m at=finish' | lcut method pathGET /providers/users/searchGET /vendor/resources/6307854GET /healthGET /vendor/resources/6007506GET /vendor/resources/7117492...
Recommended - HPE recommends users update to this version at their earliest convenience. Important Notes: This version of the System ROM contains updates aligned with the Intel Product Update (IPU) ...
针对该系统须保证任务截止期和有效性的特点,提出了一种并行EDPF(Earliest Deadline and Processing Time First)优化调度算法。该算法适用于可并行任务,并在考虑到了任务集的截止期和资源因素基础上,加入了运行...
Deriving deadlines and periods for update transactions so as to maintain timeliness and data freshness while minimizing imposed workload has long been recognized an important problem in real-time ...
time schedulability directly to the Quality of Control (QoC), the ultimate goal of a control system, a hierarchical feedback QoC management framework with the Fixed Priority (FP) and the Earliest-...
have existed: the earliest being remote job entry terminals used to submit programs to a central computer and the latest being Java applets downloaded from web servers into web browsers. A new phase...
同时 ,给出了扩展的随机 DA G 中节点的 EST ( Earliest Start Time) 计算方法 ,并以 SCP 算法为例进行实验模拟。 实验结果表明 ,SSCP 算法相对于 SCP 算法 ,减少了并行任 务执行时间 ,并能更精确地预测任务调度的...