題目

數(shù)軸上有n個閉區(qū)間[ai, bi]。取盡量少的點，使得每個區(qū)間內(nèi)都至少有一個點（不同區(qū)間內(nèi)含的點可以是同一個）。

輸入格式：

第一行一個數(shù)字n，表示有n個閉區(qū)間。 下面n行，每行包含2個數(shù)字，表示閉區(qū)間[ai, bi]

輸出格式:

一個整數(shù)，表示至少需要幾個點

輸入樣式：

在這里給出一組輸入。例如：

輸出樣式：

在這里給出相應(yīng)的輸出。例如：

基本思想：

一個點要處于盡可能多的區(qū)域內(nèi)

代碼實現(xiàn)：

#include<bits/stdc++.h> using namespace std;typedef struct{int start;int end; }area;bool cmp(area a, area b) {if(a.start==b.start) return a.end<b.end;else return a.start<b.start; }int main() {int n;cin>>n;int count=0; //考慮數(shù)軸上沒有閉區(qū)間的情況 //不過題目的測試點中沒有這種情況，可以把count直接設(shè)成1, 省略下面這個if-else判斷if(n==0){cout<<count<<endl;return 0;}else count=1;area a[n];for(int i=0; i<n; i++){cin>>a[i].start>>a[i].end;}sort(a, a+n, cmp); //因為a是結(jié)構(gòu)體，要重寫cmpfor(int i=0, j=0; i<n && j<n; ){if(a[i].end>=a[j].start) //a[i]和a[j]存在重疊部分//注意, 因為是閉區(qū)間,要考慮a[i].end和a[j].start相等的情況{j++;}else //a[i]和a[j]不存在重疊部分//新的a[i]為舊的a[j], 新的a[j]為舊的a[j+1], 繼續(xù)循環(huán){count++;i=j;j++;}}cout<<count<<endl;return 0; }

?提交結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的贪心算法 - 选点问题 (15 分) C++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。