Jobdu 1463 招聘会(任务调度, 贪心算法) - SangS - 博客园

九度 1463 招聘会(任务调度, 贪心算法) - SangS - 博客园
又到毕业季，很多大公司来学校招聘，招聘会分散在不同时间段，小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。

贪心策略简单证明：假设有两个招聘会A和B，且A的结束时间要早于B的结束时间，那么显然我们选择B的时候B的所有后续安排全部不会和A冲突，而选择A的时候A的后续却不一定满足不与B冲突。一个直观的理解就是越早完成的招聘会会给后续招聘会腾出更多时间。
https://www.cnblogs.com/easonliu/p/3639596.html

 7 struct data {
 8     int st;
 9     int ed;
10 };
11 
12 bool cmp(const data &a, const data &b) {
13     return a.ed < b.ed;
14 }
15 
17     //freopen("input.txt", "r", stdin);
18     vector<data> v;
19     data d;
20     int n;
21     int res;
22     int ed;
23     while (cin >> n) {
24         v.clear();
25 
26         for (int i = 0; i < n; ++i) {
27             cin >> d.st >> d.ed;
28             v.push_back(d);
29         }
30         sort(v.begin(), v.end(), cmp);
31         res = 1;
32         ed = v[0].ed;
33         for (int i = 0; i < n; ++i) {
34             if (v[i].st >= ed) {
35                 ed = v[i].ed;
36                 ++res;
37             }
38         }
39         cout << res << endl;
40     }

http://www.cnblogs.com/xinsheng/p/3594175.html

    while(scanf("%d", &n) != EOF) {
        vector<Meeting> meetings;
        for(int i = 0; i < n; i ++) {
            int st, ed;
            scanf("%d%d", &st, &ed);
            meetings.push_back(Meeting(st, ed));
        }

        sort(meetings.begin(), meetings.end());

        int res = 0;
        int lastpos = 0;
        for(int i = 0; i < meetings.size(); i ++) {
            if(meetings[i].st >= lastpos) {
                res ++;
                lastpos = meetings[i].ed;
            }
        }
        printf("%d\n", res);

X. Brute Force
http://www.acmerblog.com/jiudu-1463-2385.html

15	for(int i=0; i<n; i++) {

16	cin >> nodes[i].s >> nodes[i].e;

17	opt[i] = 0;

18

}

19	sort(nodes, nodes+n, cmp);

20	opt[0] = 1;

21	for(int i=1; i<n; i++) {

22	for(int j=i-1; j>=0; j--) {

23	if(nodes[i].s >= nodes[j].e) {

24	opt[i] = opt[j]+1;

25

break;

26

}

27

}

28	if(opt[i] < opt[i-1]) {

29	opt[i] = opt[i-1];

30	nodes[i].e = nodes[i-1].e;

31

}

32

}

33	cout << opt[n-1] << endl;

Read full article from 九度 1463 招聘会(任务调度, 贪心算法) - SangS - 博客园