一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2422|回复: 15
收起左侧

EA电面

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

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

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

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

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


祝大家offer多多!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

小柯西 发表于 2015-10-23 13:20:49 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
leetcode meeting rooms
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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

smart solution
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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)个时间点,把时间点按大小关系离散化就可以了

可否具体讲一下?谢谢了
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:25:04 | 显示全部楼层
lqzgz 发表于 2015-10-23 13:40. more info on 1point3acres.com
smart solution

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

使用道具 举报

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

这道题就是求最大的不重叠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):. 1point 3acres 璁哄潧
  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):
    def __init__(self, start, end):
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴        self.start = start. more info on 1point3acres.com
        self.end = end
   
    def __repr__(self):
        return '[%d, %d]' %(self.start, self.end)
   
# `intervals` is a list of intervals. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
# `time` is a interval..1point3acres缃
# 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)
   
    rst = 0
    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
   
    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)
复制代码
机智,受教了
回复 支持 反对

使用道具 举报

liqingfd 发表于 2017-1-20 09:35:11 | 显示全部楼层
dp的做法试了一下,自己跑了几个testcase感觉没什么问题,如果小伙伴们发现有错误,欢迎指出:)
  1. public class test {
  2.     static class Interval {
  3.         int start;
  4.         int end;
  5.         public Interval(int start, int end) {
  6.             this.start = start;
  7.             this.end = end;
  8.         }
  9.     }
  10.     public static int maxTask(Interval[] intervals, Interval total) {
  11.         int res = 0;
  12.         // dp[i] - until ith interval, maximum tasks
  13.         List<Integer> dp = new ArrayList<>();
  14.         Arrays.sort(intervals, new Comparator<Interval>() {
  15.             @Override
  16.             public int compare(Interval a, Interval b) {
  17.                 if (a.start != b.start)     return a.start - b.start;
  18.                 else    return a.end - b.end;
  19.             }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.         });. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.         dp.add(1);
  22.         for (int i = 1; i < intervals.length && intervals[i].end <= total.end; i++) {
  23.             dp.add(0);
  24.             for (int j = 0; j < i; j++) {
  25.                 if (intervals[j].end <= intervals[i].start) {
  26.                     if (dp.get(j) + 1 > dp.get(i)) {
  27.                         dp.set(i, dp.get(j) + 1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.                         res = Math.max(res, dp.get(i));. more info on 1point3acres.com
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.         return res;
  34.     }
  35.     public static void main(String args[]){
  36.         Interval i1 = new Interval(1, 50);
  37.         Interval i2 = new Interval(51, 100);
  38.         Interval i3 = new Interval(1, 20);
  39.         Interval i4 = new Interval(30, 40);
  40.         Interval i5 = new Interval(40, 50);
  41.         Interval i6 = new Interval(80, 90);
  42.         Interval i7 = new Interval(95, 110);
  43.         Interval[] is = new Interval[7];. 1point 3acres 璁哄潧
  44.         is[0] = i1;
  45.         is[1] = i2;
  46.         is[2] = i3;
  47.         is[3] = i4;
  48.         is[4] = i5;
  49.         is[5] = i6;
  50.         is[6] = i7;
  51.         System.out.print(maxTask(is, new Interval(1, 100)));
  52.     }
  53. }
复制代码
回复 支持 反对

使用道具 举报

shiloh00 发表于 2017-2-1 06:12:28 | 显示全部楼层
这个题想到一个o(n)的方法 其实就是和meetingroom一样但是是逆向思维 我们不妨看如果想让所有的task都run的话 最少需要多少个线程 那么把总得个数减去最小的线程数再➕1就是最后要的结果了 代码如下:
. visit 1point3acres.com for more.

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
using namespace std;
struct cmp{
        bool operator()(int a, int b){
                if(abs(a) == abs(b))
                        return a < b;
                else. From 1point 3acres bbs
                        return abs(a) < abs(b);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }. from: 1point3acres.com/bbs
}comparator;
int find_max(vector<pair<int, int>>& vec, pair<int, int>& bar){
        vector<int> res;
        int first = bar.first;
        int second = bar.second;. 1point 3acres 璁哄潧
        for(int i = 0; i < vec.size(); i++){
                if(vec[i].first >= first && vec[i].second <= second){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        res.push_back(vec[i].first);
                        res.push_back(vec[i].second * (-1));
                }
        }
//        cout << res.size() << endl;
        sort(res.begin(), res.end(), comparator);
        int Max = INT_MIN;
        int count = 0;
        for(int i = 0; i < res.size(); i++){
                if(res[i] > 0){. 1point3acres.com/bbs
                        count += 1;
                        Max = max(Max, count);
                }                               
                else{
                        count--;. more info on 1point3acres.com
                }
        }
        return res.size() / 2 - Max + 1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
int main(){. From 1point 3acres bbs
        vector<pair<int, int>> res;
        res.push_back(make_pair(1, 20));
        res.push_back(make_pair(21, 40));
        res.push_back(make_pair(1, 99));
        res.push_back(make_pair(45, 60));
        res.push_back(make_pair(70, 80));
        res.push_back(make_pair(2, 65));
        res.push_back(make_pair(1, 101));
        pair<int, int> p = make_pair(1, 100);.1point3acres缃
        int r = find_max(res, p);
        cout << r << endl; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}.鏈枃鍘熷垱鑷1point3acres璁哄潧


回复 支持 反对

使用道具 举报

hurtlocker 发表于 2017-2-9 14:02:34 | 显示全部楼层
shiloh00 发表于 2017-2-1 06:12. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个题想到一个o(n)的方法 其实就是和meetingroom一样但是是逆向思维 我们不妨看如果想让所有的task都run的 ...

这个有sort了至少是nlgn吧。。。. more info on 1point3acres.com

代码没仔细看,但是按照你叙述的思路,[[1,5], [6,10], [2, 7], [8, 12]]似乎就是反例?
显然最多可安排2个区间,答案是2.
但是按你的想法,2个“线程”就可以放下所有task,那么4-2+1=3这个答案是错的。。。

按end time排序似乎就可以。。。这里的intuition是如果end time确定,不会影响后续的安排。
假设现在已经按end time排好序,那么考察当前incoming的区间[s, e],当前总的结束时间为E,如果
1. s >= E,accept [s, e], 可安排会议数+1
2. s < E,那么[s, e]*至少*会跟一个已经安排好的区间overlap,reject [s, e]即可
因此这样iterate并且安排区间,从头到尾是“不会亏”的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-26 18:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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