一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1649|回复: 12
收起左侧

EA电面

[复制链接] |试试Instant~ |关注本帖
lqzgz 发表于 2015-10-23 12:57:36 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Electronic Arts - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
游客,本帖隐藏的内容需要积分高于 1 才可浏览,您当前积分为 0。 查看如何攒积分


祝大家offer多多!
. Waral 鍗氬鏈夋洿澶氭枃绔,
小柯西 发表于 2015-10-23 13:20:49 | 显示全部楼层
leetcode meeting rooms
回复 支持 反对

使用道具 举报

edly 发表于 2015-10-23 13:30:55 | 显示全部楼层
本质只有O(#Interval)个时间点,把时间点按大小关系离散化就可以了
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 13:34:52 | 显示全部楼层

完全是不同的题=,=
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 13:40:27 | 显示全部楼层
edly 发表于 2015-10-23 13:30
本质只有O(#Interval)个时间点,把时间点按大小关系离散化就可以了
. From 1point 3acres bbs
smart solution
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:22:54 | 显示全部楼层
dp[task.end] = dp[0..(task.start - 1)] + 1。。。这里task.end是时间点吗?dp[task.end]是不是就是dp[0..task.end]?
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:24:17 | 显示全部楼层
edly 发表于 2015-10-23 13:30
本质只有O(#Interval)个时间点,把时间点按大小关系离散化就可以了
. 1point 3acres 璁哄潧
可否具体讲一下?谢谢了
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:25:04 | 显示全部楼层

对于楼上的理解,可否具体讲一下?我觉得lz您提的followup解法就不错啊
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-24 12:00:56 | 显示全部楼层
lqzgz 发表于 2015-10-23 13:34
完全是不同的题=,=

这道题就是求最大的不重叠interval数量啊,算法导论上讲greedy的那一章专门有说过,和meeting rooms是同一个模型。只不过这题多加了个区间限制,[1, 100],不过也很好办,在每个iterration里都判断下当前检查的interval是否已经超出限制区间就行了。
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-24 12:34:08 | 显示全部楼层
小柯西 发表于 2015-10-24 12:00
这道题就是求最大的不重叠interval数量啊,算法导论上讲greedy的那一章专门有说过,和meeting rooms是同 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
alright,算法导论没好好看过。。。
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-24 12:54:38 | 显示全部楼层
  1. </blockquote><div class="blockcode"><blockquote><blockquote>class Interval(object):. from: 1point3acres.com/bbs
  2.     def __init__(self, start, end):
  3.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">self.start = start</span>
复制代码
刚才写的,思路大概就是这有
.鐣欏璁哄潧-涓浜-涓夊垎鍦


补充内容 (2015-10-24 12:55):
卧槽。怎么变成这样
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-24 12:55:27 | 显示全部楼层
class Interval(object):. 鍥磋鎴戜滑@1point 3 acres
    def __init__(self, start, end):
        self.start = start
        self.end = end
    . 1point3acres.com/bbs
    def __repr__(self):
        return '[%d, %d]' %(self.start, self.end)
    . visit 1point3acres.com for more.
# `intervals` is a list of intervals.
# `time` is a interval.
# return the max num of tasks that can be done in the given time.
def maxTaskNum(tasks, time):
    tasks.sort(key=lambda i: i.end)
    . 1point3acres.com/bbs
    rst = 0. From 1point 3acres bbs
    ongoing_task = None
   
    for task in tasks:
        if task.start < time.start: continue
        if task.end > time.end: break
        if not ongoing_task or task.start >= ongoing_task.end:
            rst += 1
            ongoing_task = task
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
    print rst


tasks = [Interval(1,50), Interval(51,100), Interval(1,99)]
time = Interval(1,100)

maxTaskNum(tasks, time)
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-24 13:33:25 | 显示全部楼层
  1. tasks.sort(key=lambda i: i.end)
复制代码
机智,受教了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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