【贪心策略】区间选点问题

问题描述：

Description

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

问题的大概意思是：给定一个闭区间，并且这个闭区间上的点都是整数，现在要求你使用最少的点来覆盖这些区间并且每个区间的覆盖的点的数量满足输入的要求点覆盖区间的数量，其中在这个区间的某些区间上要求要有特定的点来覆盖，

输入:

第一行输入的是测试样例的个数

接下来的是每个测试样例输入，其中包括区间的开始端点与结束端点，覆盖整个区间的点的数量，开始端点与结束端点都在50000之内，而且要求点的覆盖的数量在开始区间与结束区间之间

下面是我自己的见解：

对于这道题相比原始的区间选点问题还是有一定的区别的，但是此时还是要遵循一个原则：先找尽量靠右的点，因为这可能命中更多的区间。

• 首先按照区间右端点排序，然后对排序之后的区间，从第一个开始取点。
• 同时要用一个数组模拟坐标来记录某个点是否已经被选择。
• 在后面的区间判断取点之前，要先根据坐标轴上的点来判断还需要取几个点

代码及讲解：

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct interval{
  int start;
  int stop;
  int cont;
}Inter;
int n;
const int MAXN = 1001;
Inter intervals[MAXN];
bool compareInter(Inter i1, Inter i2){
  return i1.stop < i2.stop || (i1.stop == i2.stop && i1.start < i2.start);
}
int minSpots(){
  int res = 0;
  int anix[intervals[n-1].stop+1] = {0};                            //定义一个坐标轴，0表示此点没选，1表示已选 
  for(int i = 0; i < n; i++){//遍历每一个区间
    for(int j = intervals[i].stop; j-intervals[i].start >= 0; j--){             //这个循环用来检测此区间内是否已经有了点，还剩几个点
      if(anix[j] >= 1) intervals[i].cont--;
    }
    for(int j = intervals[i].stop; j-intervals[i].start >= 0 && intervals[i].cont > 0; j--){//从区间的右边开始取点，注意约束条件
      if(anix[j] >= 1) continue;                              //如果这个点已经选了，继续看下一个点
      if(intervals[i].cont <= 0) break;                       //如果已经选完了，跳出循环，看下一个区间
      res++;//选择
      intervals[i].cont--;//修改
      anix[j]++;//标记
    }
  }
  return res;
}
int main(){ 
  cin >> n; 
  for(int i = 0; i < n; i++)
    cin >> intervals[i].start >> intervals[i].stop >> intervals[i].cont;
  sort(intervals, intervals+n, compareInter);//按照区间右端点排序
  cout << minSpots() << endl;
  return 0;
}

提交到POJ上会发生超时，但是代码的逻辑是没有什么问题的，关键是在扫描每个区间的时候消耗的时间比较多导致了超时，但是我们可以使用另外的一种数据结构来解决那就是树状数组，降低扫描区间的时间复杂度