LeetCode_cplusplus/MaximumLengthofPairChain.cpp at master · stormeddy/LeetCode_cplusplus · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
//
//Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
//
//Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
//
//Example 1:
//Input: [[1,2], [2,3], [3,4]]
//Output: 2
//Explanation: The longest chain is [1,2] -> [3,4]
//Note:
//The number of given pairs will be in the range [1, 1000].

#include<vector>
#include<algorithm>

using namespace std;

class MaximumLengthofPairChain {
public:
	int findLongestChain(vector<vector<int>>& pairs) {
		sort(pairs.begin(), pairs.end(), [](vector<int>& a, vector<int>& b){return a[1]<b[1];});
		int res = 1;
		vector<int>& p = pairs[0];
		for (int i = 1; i<pairs.size(); ++i){
			if (pairs[i][0]>p[1]){
				p[1] = pairs[i][1];
				++res;
			}
		}
		return res;
	}


//public:
//	int findLongestChain(vector<vector<int>>& pairs) {
//		sort(pairs.begin(), pairs.end(), cmp);
//		int cnt = 0;
//		vector<int>& pair = pairs[0];
//		for (int i = 0; i < pairs.size(); i++) {
//			if (i == 0 || pairs[i][0] > pair[1]) {
//				pair = pairs[i];
//				++cnt;
//			}
//		}
//		return cnt;
//	}
//
//private:
//	static bool cmp(vector<int>& a, vector<int>&b) {
//		return a[1] < b[1] || a[1] == b[1] && a[0] < b[0];
//	}


	//java dp version
	//Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));

	//int i, j, max = 0, n = pairs.length;
	//int dp[] = new int[n];

	//for (i = 0; i < n; i++) dp[i] = 1;

	//for (i = 1; i < n; i++)
	//	for (j = 0; j < i; j++)
	//		if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)
	//			dp[i] = dp[j] + 1;

	//for (i = 0; i < n; i++) if (max < dp[i]) max = dp[i];

	//return max;
//	}


	//java dp version
	//Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));

	//int i, j, max = 0, n = pairs.length;
	//int dp[] = new int[n];

	//for (i = 0; i < n; i++) dp[i] = 1;

	//for (i = 1; i < n; i++)
	//	for (j = 0; j < i; j++)
	//		if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)
	//			dp[i] = dp[j] + 1;

	//for (i = 0; i < n; i++) if (max < dp[i]) max = dp[i];

	//return max;
};