首页 > 代码库 > Restaurant

Restaurant

2024-09-11 10:27:11   214人阅读

Restaurant
Time Limit:4000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u
Submit Status

Description

A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time li and the finish time ri (li ≤ ri).

Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?

No two accepted orders can intersect, i.e. they can‘t share even a moment of time. If one order ends in the moment other starts, they can‘t be accepted both.

Input

The first line contains integer number n (1 ≤ n ≤ 5·105) — number of orders. The following n lines contain integer values li and rieach (1 ≤ li ≤ ri ≤ 109).

Output

Print the maximal number of orders that can be accepted.

Sample Input

Input
2
7 11
4 7
Output
1
Input
5
1 2
2 3
3 4
4 5
5 6
Output
3
Input
6
4 8
1 5
4 7
2 5
1 3
6 8
Output
2
/*题意：给你餐厅n组客人就餐时间（起始时间，终止时间）如果时间有重叠的话，那么两组客人不能同时用餐，问餐厅最多接纳多少组客人初步思路：按照终止时间排序，然后贪心*/#include <bits/stdc++.h>using namespace std;struct node{    int Frist,End;    bool operator <(const node &other) const{        return End<other.End;    }}fr[500005];int n;int res=0;int last=0;void init(){    res=0;    last=0;}int main(){    // freopen("in.txt","r",stdin);    while(scanf("%d",&n)!=EOF){        init();        for(int i=0;i<n;i++){            scanf("%d%d",&fr[i].Frist,&fr[i].End);        }        sort(fr,fr+n);        for(int i=0;i<n;i++){            if(fr[i].Frist>last){                res++;                last=fr[i].End;            }        }        printf("%d\n",res);    }    return 0;}

 

Restaurant


联系
我们