前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Contest 176 - LeetCode 1353. Maximum Number of Events That Can Be Attended (贪心)

Contest 176 - LeetCode 1353. Maximum Number of Events That Can Be Attended (贪心)

作者头像
ShenduCC
发布2020-02-24 15:50:00
4100
发布2020-02-24 15:50:00
举报
文章被收录于专栏:算法修养

题目

题意:有n个节目,每个节目有一个持续的天数,你一天只能看一个节目,问你这么多天最多能看几个节目

题解:贪心,我们把那种截止日期最近的节目,都看了。把节目按照截止日期从小到大排序。接下来一个一个节目看,可以用数组标记的方法,for循环判断在当前节目的区间内,还有有没有天数是空闲的。

最后一步的for循环,可以用线段树代替,这样的话就是O(log(k))的效率查找当前节目是否可以观看。 k为区间的长度。

两种方法都可以过

for循环

代码语言:javascript
复制
struct Node
{
    int l;
    int r;
}b[100005];
int cmp(Node a,Node b)
{
    if(a.r==b.r)
        return a.l>b.l;
    return a.r<b.r;
}
class Solution {
public:
    int vis[100005];
    int maxEvents(vector<vector<int>>& events) {
        
        int len = 0;
        int p = 0;
        for(int i=0;i<events.size();i++)
        {
           len=max(len,events[i][1]);
           b[p].l = events[i][0];
           b[p].r = events[i][1];
           p++;
        }
        
        sort(b,b+p,cmp);
        
        int ans=0;
        for(int i=0;i<p;i++)
        {
            for(int j=b[i].l;j<=b[i].r;j++)
            {
                if(!vis[j])
                {
                    vis[j]=1;
                    ans++;
                    break;
                }
            }
        }
        return ans;
        
    }
};

线段树

代码语言:javascript
复制
struct Node
{
    int l;
    int r;
}b[100005];
int cmp(Node a,Node b)
{
    if(a.r==b.r)
        return a.l>b.l;
    return a.r<b.r;
}
class Solution {
public:
    int num[100005*4];
    int maxEvents(vector<vector<int>>& events) {
        
        int len = 0;
        int p = 0;
        for(int i=0;i<events.size();i++)
        {
           len=max(len,events[i][1]);
           b[p].l = events[i][0];
           b[p].r = events[i][1];
           p++;
        }
        
        sort(b,b+p,cmp);
        
        int ans=0;
        for(int i=0;i<p;i++)
        {
            int pos = query(1,1,len,b[i].l,b[i].r,0);
            if(pos!=-1)
            {
                ans++;
                update(1,1,len,pos,1);
            }
        }
        return ans;
        
    }
    
    void pushup(int node)
    {
        if(num[node<<1]==num[node<<1|1])
            num[node]=num[node<<1];
        else
            num[node]=-1;
    }
    
    void update(int node,int l,int r,int i,int val)
    {
        if(l==r&&l==i)
        {
            num[node]=val;
            return;
        }
        
        int mid = (l+r)/2;
        
        if(i<=mid)
            update(node<<1,l,mid,i,val);
        if(i>mid)
            update(node<<1|1,mid+1,r,i,val);
        
        pushup(node);
    }
    
    int query(int node,int l,int r,int start,int end,int val)
    {
        if(start<=l&&r<=end)
        {
            if(num[node]!=-1)
            {
                if(num[node]==val)
                    return l;
                else
                    return -1;
            }
        }
        
        int mid = (l+r)/2;
        
        int res;
        if(start<=mid)
        {
            res = query(node<<1,l,mid,start,end,val);
            if(res!=-1)
                return res;
        }
        
        if(end>mid)
        {
            res = query(node<<1|1,mid+1,r,start,end,val);
        }
        
        return res;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-02-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档