bnu-44582

昨天北师大新生赛的题，本弱做一做。。。

贪心题，按照结束时间排序进行贪心。

MLX的疯狂睡眠

Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: 

%lld      Java class name:  Main

Prev 

Submit  Status  Statistics  Discuss

Next

None

• None
• Graph Theory
•     2-SAT
•     Articulation/Bridge/Biconnected Component
•     Cycles/Topological Sorting/Strongly Connected Component
•     Shortest Path
•         Bellman Ford
•         Dijkstra/Floyd Warshall
•     Euler Trail/Circuit
•     Heavy-Light Decomposition
•     Minimum Spanning Tree
•     Stable Marriage Problem
•     Trees
•     Directed Minimum Spanning Tree
•     Flow/Matching
•         Graph Matching
•             Bipartite Matching
•             Hopcroft–Karp Bipartite Matching
•             Weighted Bipartite Matching/Hungarian Algorithm
•         Flow
•             Max Flow/Min Cut
•             Min Cost Max Flow
• DFS-like
•     Backtracking with Pruning/Branch and Bound
•     Basic Recursion
•     IDA* Search
•     Parsing/Grammar
•     Breadth First Search/Depth First Search
•     Advanced Search Techniques
•         Binary Search/Bisection
•         Ternary Search
• Geometry
•     Basic Geometry
•     Computational Geometry
•     Convex Hull
•     Pick's Theorem
• Game Theory
•     Green Hackenbush/Colon Principle/Fusion Principle
•     Nim
•     Sprague-Grundy Number
• Matrix
•     Gaussian Elimination
•     Matrix Exponentiation
• Data Structures
•     Basic Data Structures
•     Binary Indexed Tree
•     Binary Search Tree
•     Hashing
•     Orthogonal Range Search
•     Range Minimum Query/Lowest Common Ancestor
•     Segment Tree/Interval Tree
•     Trie Tree
•     Sorting
•     Disjoint Set
• String
•     Aho Corasick
•     Knuth-Morris-Pratt
•     Suffix Array/Suffix Tree
• Math
•     Basic Math
•     Big Integer Arithmetic
•     Number Theory
•         Chinese Remainder Theorem
•         Extended Euclid
•         Inclusion/Exclusion
•         Modular Arithmetic
•     Combinatorics
•         Group Theory/Burnside's lemma
•         Counting
•     Probability/Expected Value
• Others
•     Tricky
•     Hardest
•     Unusual
•     Brute Force
•     Implementation
•     Constructive Algorithms
•     Two Pointer
•     Bitmask
•     Beginner
•     Discrete Logarithm/Shank's Baby-step Giant-step Algorithm
•     Greedy
•     Divide and Conquer
• Dynamic Programming
• Tag it!

在一个寝室中，有早上6点多起床跑自习室或者图书馆，晚上11点多回寝室洗洗直接睡觉的神牛（真是神一般的存在）；也有早上11点多起来直接吃饭，下午玩一会累了又sleep的睡神；也有白天一直陪妹子，大晚上和寝室程序猴子作伴的泡神；也有早上不知道何时起，从下午到第二天早些时候（确实早啊！）一直code的神码手····那么现在问题来了，寝室本来是一个非常友好的team，但是为了证明自己的睡眠行为是大学最完美的，他们决定来一场惊天地的辩论····MLX作为寝室的一员，突然做出一个疯狂的决定：统计出寝室每一个成员的睡眠时间段（每一个成员可能有多个睡眠时间段），然后将亲自实践每一个成员睡眠方式，然后再决定谁的更好。聪明的您可能会想这样一个问题：如果MLX从进入一个睡眠段开始到结束中途不醒，MLX那一天最多能睡多少次？

现在将问题进一步抽象为：一天内有n个睡眠区间，每一个睡眠区间分别为距离当天0点的第Si秒开始，第Ti秒结束。对于每一次睡眠，MLX都可以参与或者不参与，如果选择了，那么MLX就必须将本次睡眠进行到底。此外，参与睡眠的时间不能重复（即使是刚开始的瞬间和结束的瞬间的重复也是不允许的），请问MLX最多能参与多少次睡眠？

Input

第一行输入T，表示T组测试数据。

每一组的第一行输入n，表示有n个睡眠区间（1<= n <=10^5 ）

接下来n行，每一行输入两个整数Si，Ti（空格隔开），表示睡眠区间的开始和结束时间（1<= Si< Ti< 24*3600）

Output

MLX最多参与的睡眠次数

Sample Input

1 5 1 3 2 5 4 7 6 9 8 10

Sample Output

3

Hint

参与的睡眠编号依次是（1,3,5）

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>
#include<time.h>
#include<utility>
#include<malloc.h>

using namespace std;

int n;

struct Q
{
	int s;
	int e;
}p[100010];

bool cmp(Q a, Q b)
{
	return a.e < b.e;
}

int cases;

int main()
{
	cin >> cases;

	while (cases--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> p[i].s >> p[i].e;

		sort(p+1,p+1+n,cmp);

		int ans = 1;
		int t = p[1].e;

		for (int i = 2; i <= n; i++)
		{
			if (t < p[i].s)
			{
				ans++; 
				t = p[i].e;
			}
		}
		cout << ans << endl;
	}
	return 0;
}