一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 536|回复: 14
收起左侧

[动态规划] 求这道面经题的解法

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
user123456 发表于 2019-6-10 11:02:38 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (60)
 
 
6% (4)    👎
5小米
给你一堆Events,每个Event有start time和end time。Events的时间可能overlap。计算一个人当天最多可以参加几个events。



上一篇:转码master暑期没实习该如何度过
下一篇:最少修改次数还原航线
我的人缘0
moluren 发表于 2019-6-10 22:01:30 | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   90% (378)
 
 
9% (39)    👎
这道题貌似与以下interval相关的题目类似:
给定一堆interval,问最多的不相交的interval的个数是多少。

对于interval的问题,基本方法就是两个:排序然后使用贪心算法。
贪心算法的策略是:排序后,两个相交的interval移除EndTime大的那个。

回到楼主题目,我建议的思路是:排序,使用贪心算按天统计不相交的interval(Event)的数量。

补充内容 (2019-6-10 22:02):
时间复杂度:整体排序O(NLogN),计算不相交的Interval数需要进行一次O(N)遍历。
因而整体时间复杂度是O(NLogN)
回复

使用道具 举报

我的人缘0
337845818 发表于 2019-6-11 05:40:27 | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   75% (239)
 
 
24% (79)    👎
背包题目, 经典greedy题目.
按结束时间排序即可
回复

使用道具 举报

我的人缘0
 楼主| user123456 发表于 2019-6-11 08:34:47 | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   93% (60)
 
 
6% (4)    👎
感觉greedy似乎不行。给个反例:
Events = [1, 10], [2, 15], [11, 50], [12, 13], [13, 14]
这样Greedy排出来是这么三排不overlap的时间:
[1, 10], [11, 50]
[2, 15],
[12, 13], [13, 14]
即最多是2。但下面这种选法是3:
[1, 10], [12, 13], [13, 14]
回复

使用道具 举报

我的人缘0
wisdompeak2 发表于 2019-6-11 09:22:50 | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   99% (196)
 
 
0% (1)    👎
贪心法。按结束时间排序。思想是:结束时间早的区间,因为对后续的影响最小,所以我们会优先收录。
所以,我们肯定会收录第一个区间后,接着顺次考察后续的区间,只要与第一个区间重叠的都会舍弃不看,直至找到下一个与第一个区间没有重叠的区间。这是最早结束的、与第一个区间无重叠的区间,因此是最优的,收录其中。
然后重复以上的步骤,直至考察完所有的区间。

评分

参与人数 1大米 +1 收起 理由
user123456 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| user123456 发表于 2019-6-11 17:20:06 | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   93% (60)
 
 
6% (4)    👎
wisdompeak2 发表于 2019-6-11 09:22
贪心法。按结束时间排序。思想是:结束时间早的区间,因为对后续的影响最小,所以我们会优先收录。
所以, ...

感觉这个方法讲得通。但还是没有说服自己为什么这么做一定是对的。即有没有可能在某一步选择最先结束的时候并不是最优的方案?不知道怎么证明这个是不可能的。
回复

使用道具 举报

我的人缘0
 楼主| user123456 发表于 2019-6-11 17:21:43 | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   93% (60)
 
 
6% (4)    👎
参考楼上说的方法,写了一个代码。暂时没有找到反例:

[Java] 纯文本查看 复制代码
import java.util.*;

public class Solution {
  public static void main(String[] args) {
    Event[] events = new Event[] {
      new Event(1, 5),
      new Event(1, 4),
      new Event(2, 3),
      new Event(3, 4),
      new Event(4, 5),
    };
    List<Event> res = (new MyCode()).getMaxEvents(events);
    System.out.println(res.size());
    for(Event ev : res) {
      ev.print();
    }
  }
}

class MyCode {
  public List<Event> getMaxEvents(Event[] events) {
    List<Event> res = new LinkedList<>();
    if (events.length == 0) {
      return res;
    }
    Arrays.sort(events, (e1, e2) -> e1.e - e2.e); // 按照结束时间从小到大排序
    res.add(events[0]);
    int lastEnd = events[0].e;
    for (int i = 1; i < events.length; i++) {
      Event curr = events[i];
      if (curr.s >= lastEnd) {
        res.add(curr);
        lastEnd = curr.e;
      }
    }
    return res;
  }
}

class Event {
  int s;
  int e;
  public Event(int s, int e) {
    this.s = s;
    this.e = e;
  }
  public void print() {
    System.out.print("[" + this.s + ", " + this.e + "] ");
  }
}
回复

使用道具 举报

我的人缘0
wisdompeak2 发表于 2019-6-11 17:31:21 | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   99% (196)
 
 
0% (1)    👎
user123456 发表于 2019-6-11 17:20
感觉这个方法讲得通。但还是没有说服自己为什么这么做一定是对的。即有没有可能在某一步选择最先结束的时 ...

你不选择最先结束的区间的话,难道会选择晚结束的区间,去占用未来宝贵的时间资源吗?
回复

使用道具 举报

我的人缘0
 楼主| user123456 发表于 2019-6-11 17:58:44 来自一亩三分地官方APP | 显示全部楼层
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   93% (60)
 
 
6% (4)    👎
wisdompeak2 发表于 2019/06/11 17:31:21


你不选择最先结束的区间的话,难道会选择晚结束的区间,去占用未来宝贵的时间资源吗?

Hmm...这个似乎是在用假设证明基于这个假设的结论
回复

使用道具 举报

我的人缘0
本楼:   0% (0)
 
 
0% (0)  
全局: 👍   91% (102)
 
 
8% (9)    👎
user123456 发表于 2019/06/11 08:34:47
感觉greedy似乎不行。给个反例:
Events = [1, 10], [2, 15], [11, 50], [12, 13], [13, 14]
这样Greedy排出来是这么三排不overla...

按结束时间sort
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-7-21 16:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表