主题:[讨论]pascal求解
吃糖果
【题目描述】
小头是个聪明的孩子,同时他也很馋嘴。鉴于上次单元考小头拿了全班第一,妈妈买来一堆糖果奖励小头,并且对小头说:“妈妈知道你很喜欢吃糖果,但是今天的糖果是特殊的,每一颗糖果都需要花一个特定的时间段来吃,并且在这段时间里你不能吃其他糖果。所以到底能吃多少颗糖果就看你的本事了。”
妈妈一共买了n颗糖果,用1、2、3……n编号,对于第i颗糖果有Li和Ri,表示小头需要用[Li,Ri]这段时间来吃掉第i颗糖果。显然如果小头要同时吃掉第i颗和第j,那么必须满足(Ri<Lj)或者(Li>Rj)。
贪吃的小头自然想吃掉尽量多的糖果,但是在美味的糖果面前,小头的智商瞬间降为负值,连1+1都变成了绝世难题。于是好心的你决定发挥雷锋精神,告诉小头他最多能吃多少颗。假设时间无限。
【输入格式】
第一行一个正整数n,表示有n颗糖果
接下来n行每行两个正整数,Li、Ri 表示第i颗糖果的时间段
【输出格式】
仅包含一个数,即小头最多能吃多少颗糖果
【样例输入】
5
2 4
1 7
10 11
4 5
5 8
【样例输出】
3
【样例解释】
选择第(1,3,5)颗糖果,他们时间段分别为[2,4]、[5,8]、[10,11]互不干扰。
【数据规模】
40%的数据,n≤10,1≤Li≤Ri≤100
80%的数据,n≤1000,1≤Li≤Ri≤10000
100%的数据,n≤100000,1≤Li≤Ri≤1000000000
【题目描述】
小头是个聪明的孩子,同时他也很馋嘴。鉴于上次单元考小头拿了全班第一,妈妈买来一堆糖果奖励小头,并且对小头说:“妈妈知道你很喜欢吃糖果,但是今天的糖果是特殊的,每一颗糖果都需要花一个特定的时间段来吃,并且在这段时间里你不能吃其他糖果。所以到底能吃多少颗糖果就看你的本事了。”
妈妈一共买了n颗糖果,用1、2、3……n编号,对于第i颗糖果有Li和Ri,表示小头需要用[Li,Ri]这段时间来吃掉第i颗糖果。显然如果小头要同时吃掉第i颗和第j,那么必须满足(Ri<Lj)或者(Li>Rj)。
贪吃的小头自然想吃掉尽量多的糖果,但是在美味的糖果面前,小头的智商瞬间降为负值,连1+1都变成了绝世难题。于是好心的你决定发挥雷锋精神,告诉小头他最多能吃多少颗。假设时间无限。
【输入格式】
第一行一个正整数n,表示有n颗糖果
接下来n行每行两个正整数,Li、Ri 表示第i颗糖果的时间段
【输出格式】
仅包含一个数,即小头最多能吃多少颗糖果
【样例输入】
5
2 4
1 7
10 11
4 5
5 8
【样例输出】
3
【样例解释】
选择第(1,3,5)颗糖果,他们时间段分别为[2,4]、[5,8]、[10,11]互不干扰。
【数据规模】
40%的数据,n≤10,1≤Li≤Ri≤100
80%的数据,n≤1000,1≤Li≤Ri≤10000
100%的数据,n≤100000,1≤Li≤Ri≤1000000000