Cleaning Shifts
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10970 | Accepted: 2877 |
Description
Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.
Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.
Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.
Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.
Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.
Input
* Line 1: Two space-separated integers: N and T
* Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.
* Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.
Output
* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.
Sample Input
3 10 1 7 3 6 6 10
Sample Output
2
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
INPUT DETAILS:
There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.
OUTPUT DETAILS:
By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.
INPUT DETAILS:
There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.
OUTPUT DETAILS:
By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.
题意:
给出 n(1 ~ 25000),t(1 ~ 1000000),代表有 n 个区间,总长为 t,寻找最小的区间使之覆盖整个区间 1 ~ t。输出最小的区间数。
思路:
贪心。将起点从小到大排序一遍,每次选择到达最远的终点的区间,直到 t 为止,如果不到达则立即跳出循环输出 -1。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef struct { int s, e; }node; node no[25005]; bool cmp (node a, node b) { return a.s < b.s; } int main() { int n, t; scanf("%d%d", &n, &t); for (int i = 0; i < n; ++i) scanf("%d%d", &no[i].s, &no[i].e); sort(no, no + n, cmp); int ans = 0, i = 0, ee = 0; while (i < n) { int max_ee = 0; while (i < n && (no[i].s <= ee || no[i].s == ee + 1)) { if (no[i].e > max_ee) { max_ee = no[i].e; } ++i; } if (max_ee) { ee = max_ee; ++ans; } else break; if (ee == t) break; } if (ee == t) printf("%d\n", ans); else printf("-1\n"); return 0; }
相关推荐
Shifts in microbial community under different fertilizers in a lab incubation,张奇春,王光火,The effects of different fertilization treatments on paddy soil microbial communities were characterized ...
监控一系列均值漂移的广义累积和控制图,周勤,罗陨照,本文提出监控一系列均值漂移的广义累积和(GCUSUM)控制图, 不依赖于事先设定的漂移大小.同时为了简化运算提出了对GCUSUM的修正(MGCUSUM)并�
The shifts were observed to correlate well with the shifts in the trends of pH and exit carbon dioxide profiles. To exemplify, the ammonia uptake and nitrate uptake phases were marked by a decreasing...
Power Automate模板,使您能够在Microsoft Teams Shifts中自动化操作 微软团队转变动力自动化模板 Microsoft Teams中Shifts应用程序的Power Automationate模板 电源自动化模板 Power Automate / Flow模板模板现已...
德勤:Slow growth in wages:Is the reason occupational shifts
有关于M-亚正规权移位算子和可亚正规权移位算子的一些注记,葛斌,周庆梅,设W是H上的以{an}∞n=0为权序列的单边移位算子。本文研究了M-亚正规权移位算子和可亚正规权移位算子的关系。主要结果为定理4.1和定理4
frame_shifts 预测基因组框架移位的代码
This transform cross-multiplies a function against the Haar wavelet with various shifts and stretches, like the Fourier transform cross-multiplies a function against a sine wave with two phases and ...
Tiny but universal beam shifts occur when a polarized light beam is reflected upon a planar interface. Although the beam shifts of Gaussian beams have been measured by the weak measurement technique, ...
这个pdf文件是有关盲源分离的很好的文章,文章的作者多年从事这方面的工作。
质疑宇宙红移的多普勒式表述,刘建民,,宇宙红移的多普勒式表述把宇宙红移归因于来自远行星系光讯号的多普勒效应。本文质疑了宇宙红移的这一表述。这个表述没有抓住宇宙
7shifts_String_Calculator
RNN-shifts
基于似然比的监控均值漂移的控制图,罗陨照,李忠华,文献中现有的大多监测均值的方法多基于均值变化是常数.然而这些方法在均值带有形式时效果不好. 本文基于指数滑动平均(EWMA)和广义似
下载存储库后,通过主目录中的Phenological Phenological-shifts-germany.Rproj在RStudio中打开项目。 renv应该会自动安装 要安装所有必需的软件包,只需调用renv::restore() 要运行分析,需要下载一些其他数据集...
语言:English 餐馆经理的更多信息 7shifts Chrome扩展程序,使管理员和管理员可以轻松查看谁在工作。
从概念上失败:基于概念的数据集转换说明描述尽管机器学习技术在广泛的视觉任务中表现出色,但它们通常会屈服于数据分布的变化。 因此,最近的一系列工作探索了检测这些偏移的技术。 不幸的是,当前的技术没有提供...
The phase shifts of the extinction and refractive index gratings to the illumination pattern are revealed in doped polymethyl methacrylate (PMMA). The dynamic process of these shifts is studied via ...
Moving Target Localization in Multistatic Sonar by Differential Delays and Doppler Shifts