EA电面

1. </blockquote><div class="blockcode"><blockquote><blockquote>class Interval(object):
   
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):
卧槽。怎么变成这样

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

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

1. tasks.sort(key=lambda i: i.end)

复制代码

机智，受教了

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. }

复制代码

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

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

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

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