[ POJ]1201 Intervals 区间选点问题 贪心策略
https://cn.vjudge.net/problem/POJ-1201 题目 给定n个封闭整数区间[ai, ...

12
2019/08

# [ POJ]1201 Intervals 区间选点问题 贪心策略

https://cn.vjudge.net/problem/POJ-1201

Intervals

## Intervals

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.

### Input

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

### Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

### Sample Input

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

### Sample Output

6

## 代码

package POJ;

import java.util.Scanner;

import static java.util.Arrays.sort;

public class _1201_Intervals {
static int n;

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
Interval[] jobs = new Interval[n];
int max = -1;
for (int i = 0; i < n; i++) {
jobs[i] = new Interval(cin.nextInt(), cin.nextInt(), cin.nextInt());
}
sort(jobs);
max = jobs[n - 1].t;//排序过后最大的在最后 t是结束位置
int[] rec = new int[max + 1];//标记数轴上的点是否已标记
for (int i = 0; i < n; i++) {
int s = jobs[i].s;//起点
int t = jobs[i].t;//终点
int cnt = sum(rec, s, t);//找到这个区间已经选段的数量 sum[t]~sum[s-1]
jobs[i].c -= cnt;//需要点的数量
while ((jobs[i].c > 0)) {
if (rec[t] == 0) {//从终点开始选点
rec[t] = 1;
jobs[i].c--;//个数减少
t--;//终点左移
} else
t--;
}

}
System.out.println(sum(rec,0,max));
}

private static int sum(int[] rec, int s, int t) {
int sum = 0;
for (int i = s; i <= t; i++) {
sum += rec[i];
}
return sum;
}

public static class Interval implements Comparable<Interval> {
int s, t, c;

public Interval(int s, int t, int c) {
this.s = s;
this.t = t;
this.c = c;
}

@Override
public int compareTo(Interval o) {
int x = this.s - o.s;
if (x == 0) {
return this.t - o.t;
}
return x;
}
}
}

百度已收录

Last modification：August 12th, 2019 at 06:56 pm