首页 / 算法 / 【算法学习笔记】51. 区间排序问题 SJTU OJ 1360 偶像丁姐的烦恼

【算法学习笔记】51. 区间排序问题 SJTU OJ 1360 偶像丁姐的烦恼

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法学习笔记】51. 区间排序问题 SJTU OJ 1360 偶像丁姐的烦恼，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3607字，纯文字阅读大概需要6分钟。

内容图文

Description

成为LL冠军的人气偶像丁姐最近比较烦，许多商业活动找上门来。因为每次商业活动给的毛爷爷都一样，所以丁姐希望能够尽可能多的参加这些活动。然而，商业活动的起止时间并不由丁姐说了算，因此丁姐想写一个程序，求出他最多能够参加的商业活动的数量。

Input Format

第一行一个数n，表示可选活动的数量。

接下n行每行两个数，表示每个活动开始时间t1_i和结束的时间t2_i。

Output Format

一个数字，表示丁姐最多能够参加的活动的数量。

Sample Input

                    10
0 3
0 5
10 13
12 15
2 6
4 8
9 11
13 18
14 16
15 20

Sample Output

                    5

Hint

样例选取的活动时间为：(0, 3), (4, 8), (9, 11), (12, 15), (15, 20)

n≤100000

0≤t1_i＜t2_i≤1000000

 
 
 
 
思路1.按左端排序 (同左则按右)
错误代码如下:
技术分享 技术分享 
#include <iostream>
#include <algorithm>
usingnamespace std;
 
struct Period
{
    int start;
    int end;
};
 
//按照start排序int cmp_period(constvoid* _a, constvoid* _b){
    Period* a = (Period*) _a;
    Period* b = (Period*) _b;
    if((*a).start != (*b).start)
        return (*a).start - (*b).start;
       elsereturn (*a).end - (*b).end;
}
 
Period ps[100001];
 
int main(int argc, charconst *argv[])
{
    
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i){
        
        cin>>ps[i].start>>ps[i].end;
    }
    
    qsort(ps,n,sizeof(Period),cmp_period);
    
    // for (int i = 0; i < n; ++i)
    // {
    //     cout<<ps[i].start<<" "<<ps[i].end<<endl;
    // }int cur = ps[0].start;
    int index = 0;
    int ans = 1;
    while(1){
        cur = ps[index].end;
        index++;
        for(;index < n; index++){
            if(ps[index].start >= cur){
                if(index<n-1 and ps[index+1].end < ps[index].end)
                    index++;
                ans++;
                break;
            }
        }
        if(index >= n-1)
            break;
    }
    cout<<ans<<endl;
    return0;
}
错误代码1
样例经过排序后则是
0 3
0 5
2 6
4 8
9 11 
10 13
12 15
13 18
14 16
15 20
 
第一直觉是先选择第一个区间，然后选择左端点大于等于第一个区间右端点的第一个区间，(4,8) 然后以此类推。因为同样的起点里，肯定选择的是尾部更小的。
但是这种方法会产生一个问题就是，遇到了完全重合区间没有办法延伸。
比如
0 3
3 9
4 8
8 9
按刚才的算法回选择 0 3, 3 9 但是实际上应该是 0 3, 4 8, 8 9
原因在于4,8是完全含于3,9的，所以我们要选择4,8并继续进行下去
 
所以要在这个基础上进行修改。
（另，可以暂时放弃跳过所有相同头部的这个想法。。。）
注意 核心计算的部分应该是个在线算法（O(n)）这也暗示着无论何时停止都应该得到当前的结果
先拿到0,3
再更新为 3 9
2个
此时又来了一个4 8 我们要去看4 8 与 3 9的关系
首先4>=3是一定的 因为排序过，所以只要确定两个结尾的大小即可。
发现如果新元素的尾部小于旧元素的尾部，可以把3 9 删去 换为 4 8
因为删一个 增一个 所以ans不变，但是尾部要更新为8
所以只需多维护一个变量 cur 即可 表示当前结果的尾部的数字。（其实这点就是在暗示，按尾部排序更方便，这个维护的过程其实就是排序尾部的过程。）
正确代码如下：
技术分享 技术分享 
#include <iostream>
#include <algorithm>
usingnamespace std;
 
struct Period
{
    int start;
    int end;
};
 
//按照起始点排序 int cmp_period(constvoid* _a, constvoid* _b){
    Period* a = (Period*) _a;
    Period* b = (Period*) _b;
    if((*a).start != (*b).start)
        return (*a).start - (*b).start;
       elsereturn (*a).end - (*b).end;
}
 
Period ps[100001];
 
int main(int argc, charconst *argv[])
{
    
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i){
        
        cin>>ps[i].start>>ps[i].end;
    }
    
    qsort(ps,n,sizeof(Period),cmp_period);
    
    int cur = ps[0].end;
    int ans = 1;
    for (int i = 1; i < n; ++i)
    {
        if(ps[i].start >= cur){
            cur = ps[i].end;
            ans++;
        }
        if(ps[i].end < cur)
            cur = ps[i].end;
    }
    cout<<ans<<endl;
    return0;
}
思路1正确代码

 

思路2:按右端排序，直接遍历选举所有开始时间大于当前终止时间的节点，不断维护更新终止时间即可。

用枪哥的话说，这其实是个贪心的策略，越早结束说明可以越早的参加其他的活动，所以要对尾端进行排序。

代码很简单，如下：

技术分享 技术分享 
#include <iostream>
#include <algorithm>
usingnamespace std;

struct Period
{
    int start;
    int end;
};

//按照end排序int cmp_period(constvoid* _a, constvoid* _b){
    Period* a = (Period*) _a;
    Period* b = (Period*) _b;
    //if((*a).end != (*b).end)return (*a).end - (*b).end;
       //else
     //   return (*a).start - (*b).start;}

Period ps[100001];

int main(int argc, charconst *argv[])
{
    
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i){
        
        cin>>ps[i].start>>ps[i].end;
    }
    
    qsort(ps,n,sizeof(Period),cmp_period);
    int ans = 1;
    int cur = ps[0].end;
    for (int i = 1; i < n; ++i)
    {
        if(ps[i].start >= cur){
            cur = ps[i].end;
            ans++;
        }
    }

    cout<<ans<<endl;
    return0;
}

/*
10
0 3
0 5
10 13
12 15
2 6
4 8
9 11
13 18
14 16
15 20 

*/
思路2正确代码

 

 
 

原文：http://www.cnblogs.com/yuchenlin/p/sjtu_oj_1360.html

内容总结

以上是互联网集市为您收集整理的【算法学习笔记】51. 区间排序问题 SJTU OJ 1360 偶像丁姐的烦恼全部内容，希望文章能够帮你解决【算法学习笔记】51. 区间排序问题 SJTU OJ 1360 偶像丁姐的烦恼所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1293869.html

来源：【匿名】