EA电面

您好！
本帖隐藏的内容需要积分高于 1 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 1 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

祝大家offer多多！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

leetcode meeting rooms

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));
    
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];
    
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. }

复制代码

本质只有O(#Interval)个时间点，把时间点按大小关系离散化就可以了

小柯西 发表于 2015-10-23 13:20
leetcode meeting rooms

完全是不同的题=，=

edly 发表于 2015-10-23 13:30
本质只有O(#Interval)个时间点，把时间点按大小关系离散化就可以了

smart solution

dp[task.end] = dp[0..(task.start - 1)] + 1。。。这里task.end是时间点吗？dp[task.end]是不是就是dp[0..task.end]?

edly 发表于 2015-10-23 13:30
本质只有O(#Interval)个时间点，把时间点按大小关系离散化就可以了

可否具体讲一下？谢谢了

lqzgz 发表于 2015-10-23 13:40
smart solution

对于楼上的理解，可否具体讲一下？我觉得lz您提的followup解法就不错啊

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

小柯西 发表于 2015-10-24 12:00
这道题就是求最大的不重叠interval数量啊，算法导论上讲greedy的那一章专门有说过，和meeting rooms是同 ...

alright，算法导论没好好看过。。。