A选择不相交区间。数轴上有n个开区间(a i , b i )。选择尽量多个区间，使得这些区间两两没有公共点。贪心策略是：一定要选第一个区间。

这个问题典型的是活动安排问题：

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

将所有活动按照结束时间的非递减顺序排序

template<class Type>

void GreedySelector(int n, Type s[], Type f[], bool A[])

{

       A[1]=true;

       int j=1;

       for (int i=2;i<=n;i++) {

          if (s[i]>=f[j]) { A[i]=true; j=i; }

          else A[i]=false;

          }

}

B 区间选点问题。数轴上有n个闭区间[a i , b i ]。取尽量少的点，使得每个区间内都至少有

一个点（不同区间内含的点可以是同一个）。此处的贪心策略是：取最后一个点。

将所有区间按b从小到大排序，b相同时，按照a从大到小排序。

证明：

为了方便起见，如果区间i内已经有一个点被取到，我们称区间i被满足。

1、首先考虑区间包含的情况，当小区间被满足时大区间一定被满足。所以我们应当优先选取小区间中的点，从而使大区间不用考虑。

      按照上面的方式排序后，如果出现区间包含的情况，小区间一定在大区间前面。所以此情况下我们会优先选择小区间。

      则此情况下，贪心策略是正确的。

2、排除情况1后，一定有a1<=a2<=a3……。

 

  对于区间1来说，显然选择它的右端点是明智的。因为它比前面的点能覆盖更大的范围。从而此情况下，贪心策略也是正确的。

POJ1328

Radar Installation

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 107673		Accepted: 23906

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d. 

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates. 

 
Figure A Sample Input of Radar Installations

 

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. 

The input is terminated by a line containing pair of zeros 

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Sample Input

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

ac代码:

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
//#include <bits/stdc++.h>
using namespace std;
struct island
{
    int x, y;
}is[1050];
struct qujian
{
    double be, en;
}qj[1050];
bool cmp(qujian a, qujian b)
{
    if(a.en==b.en)
        return a.be > b.be;
    return a.en < b.en;
}
int main()
{
    int n, d, case_cnt = 0;//记录case数
    while(scanf("%d%d", &n, &d)==2&&n&&d)
    {
        int Count = 1, flag = 0;//记录安装雷达数
        case_cnt++;
        int maxn = -1;
        for(int i=0; i<n; i++)
        {
            scanf("%d%d", &is[i].x, &is[i].y);
            double len = sqrt(d*d-is[i].y*is[i].y);
            qj[i].be = is[i].x-len;
            qj[i].en = is[i].x+len;
            maxn = max(maxn, is[i].y);
        }
        if(maxn>d||d<0)
        {Count = -1;flag = 1;}
        //这里一定要记得无解的话输出-1，但是前面也要加case 不能只输出-1
        if(!flag)
        {
        sort(qj, qj+n, cmp);
//        for(int i=0; i<n; i++)
//            cout << "**" << qj[i].be << " " << qj[i].en << endl;
        int j = 0;
        for(int i=1; i<n; i++)
        {
            if(qj[i].be>qj[j].en)
            {j = i;Count++;}
//设区间【a，b】选定第一个区间作为当前区间，在第一个区间的b点安装雷达
//如果下一个待检测区间的a小于等于当前区间的b则无需安装新的，否则要安装新的，并且把当前区间改为该待检测区间
//        cout << "*" << j << "*" << endl;
        }
        }
        printf("Case %d: ", case_cnt);
        printf("%d\n", Count);
    }
    return 0;
}
这道题就是得注意那个-1的情况，不能只输出-1，还要加case~QAQ

C区间覆盖问题。数轴上有n个闭区间[a i , b i ]，选择尽量少的区间覆盖一条指定线段[s,t].

 

本题的突破口仍然是区间包含和排序扫描，不过先要进行一次预处理。每个区间在[s, t]外的部分都应该预先被切掉，因为它们的存在是毫无意义的。预处理后，在相互包含的情况下，小区间显然不应该考虑。

把各区间按照a从小到大排序。如果区间1的起点不是s，无解（因为其他区间的起点更大，不可能覆盖到s点），否则选择起点在s的最长区间。选择此区间[a i , b i ] 后，新的起点应该设置为b i ，并且忽略所有区间在b i 之前的部分，就像预处理一样。虽然贪心策略比上题复杂，但是仍然只需要一次扫描，如图8-9所示。s为当前有效起点（此前部分已被覆盖），则应该选择区间2。

poj2376

Cleaning Shifts

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 31309		Accepted: 7697

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.

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.

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.

Source

USACO 2004 December Silver

Come on baby~哈哈

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node
{
    int be,en;
}cow[30000];
bool cmp(node a, node b)
{
//    if(a.be==b.be)
//        return a.en > b.en;
    return a.be < b.be;
}
int main()
{
    int n, t;
    scanf("%d %d", &n, &t);
    for(int i=0; i<n; i++)
    {
        scanf("%d %d", &cow[i].be, &cow[i].en);
    }
    sort(cow, cow+n, cmp);
//    for(int i=0; i<n; i++)
//    {
//        cout << cow[i].be << " " << cow[i].en << endl;
//    }
    int cow_cnt = 0;
    int bb = 0, ee = 0, index = 0, flag = 0;
    while(ee<t)
    {
        bb = ee + 1;
    for(int i=index; i<n; i++)
    {
        if(cow[i].be<=bb)
        {
            if(cow[i].en>=bb)
            {
                ee = max(ee, cow[i].en);
            }
        }
        else
        {
            index = i;
            break;
        }
    }
    if(bb > ee)
    {
        flag = 1;
        break;
    }
    else
    {
      cow_cnt++;
    }
    }
    if(!flag)
    cout << cow_cnt << endl;
    else
    cout << "-1\n";
    return 0;
}