Snap新鲜出炉电面挂经...哭...求大米安慰

似乎没有见过的题目，当天很不在状态，连brute-force的方法也没有写出来，被据在情理之中。

上题目：

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

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

最开始想的是greedy，然后很快发现不行。后来想着仿照minimum classroom的思路来做 - 还是greedy的思路。分析到一半还是发现不行。然后面试官让brute-force写。想着写一个dfs，但当时心态可能已经崩了，所以brute-force也没有写完。

大家有什么好的思路吗？

求大米安慰

1. public static void main(String[] args) {
   
2.         Playground pg = new Playground();
   
3.         int[][] intervals1 = new int[][]{{1,3}, {4,10}, {4,6}, {9,10}};
   
4.         int[][] intervals2 = new int[][]{{1,3}, {8,9}, {2,100}, {99, 300}};
   
5.         System.out.println(pg.getMaxProfit(intervals1));        System.out.println(pg.getMaxProfit(intervals2));
   
6.     }
   
7.   
   
8.     public int getMaxProfit(int[][] intervals){
   
9.         Arrays.sort(intervals, (a,b) -> (a[1] - b[1]));
   
10.         int n = intervals.length;
    
11.         int[] dp = new int[n];
    
12.         int max = 0;
    
13.         for(int i = 0; i < n; i++) {
    
14.             dp[i] = intervals[i][1] - intervals[i][0]; // initial value is the current interval
    
15.             for(int j = 0; j < i; j++) {
    
16.                 if(intervals[i][0] >= intervals[j][1]) {
    
17.                     dp[i] = Math.max(dp[i], dp[j] + intervals[i][1] - intervals[i][0]); // dp[i] represents the maximum profit on if ith interval is included
    
18.                     max = Math.max(max, dp[i]);
    
19.                 }
    
20.             }
    
21.         }
    
22.         return max * 100;
    
23.     }
    

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

思路
对于任意一个interval，以它结尾的合理schedule的所有可能性是：它自己加上比他早结束的任意0个，1个或多个 intervals。
因为所有interval的时间跨度都是正数，所以可以贪心地认为以某个interval结束的schedule所包含的intervals最多的那个就代表了以它结束的最大收益。
为了方便地找比当前结束更早的interval，我们可以按interval 结束的时间从小到大排序（开始时间怎么排都无所谓）。

code

1. class Solution {
   
2.     public int maxProfitAirBnb(int[][] reservations) {
   
3.         Arrays.sort(reservations, ((o1, o2) -> o1[1] - o2[1]));
   
4.         
   
5.         int res = 0;
   
6.         int[] memo = new int[reservations.length];
   
7. 
   
8.         for (int i = 0; i < reservations.length; i++) {
   
9.             int max = 0;
   
10.             for (int j = 0; j < i; j++) {
    
11.                 if (reservations[j][1] <= reservations[i][0]) {
    
12.                     max = Math.max(max, memo[j]);
    
13.                 }
    
14.             }
    
15.             memo[i] = max + (reservations[i][1] - reservations[i][0]);
    
16.             res = Math.max(res, memo[i]);
    
17.         }
    
18. 
    
19.         return res * 100;
    
20.     }
    
21. }

复制代码

猜dp？sort by end time first

GenesisXXX 发表于 2019-5-17 11:37
猜dp？sort by end time first

当时写dfs的时候，也有想着加一个memoization，但不知道memoize什么，或者说dp的公式是什么

对所有的reversation每天都是100？还是不同的给不同的价格

先根据end sort，[s1,e1], [s2,e2]...[si,ei]...，然后dp[i]代表截止到第i天的结果，dp[i]只有当i属于e的时候再更新，否则就等于dp[上一个e]的结果因为反正也没法租出去。当i属于e的时候，假设等于ej, 那么过一遍所有interval以ej结尾的，看他们要不要租，大概就是dp[i] = max(dp[i] （不租）, (ej-sj)*100 + dp[sj-1] （租）)。这样行吗

好奇呀. snap现在行业内的地位如何呢?

和meeting room有什么区别吗？应该就是只有一个房间然后尽可能多的安排meeting吧。我想的是按照start 排序，然后看下一个的start有没有和当下的end冲突，不知道这个思路怎么样？

1. public class MaxIncome {
   
2.     public static int solution(int[][] intervals) {
   
3.         Arrays.sort(intervals, (o1, o2) -> (o1[1] - o2[1]));
   
4.         int[] dp = new int[intervals[intervals.length - 1][1] + 1];
   
5.         dp[0] = 0;
   
6.         int max = 0;
   
7.         for (int[] interval : intervals) {
   
8.             int from = interval[0];
   
9.             int to = interval[1];
   
10.             int before = 0;
    
11.             for (int i = 0; i < from; i++) {
    
12.                 before = Math.max(dp[i], before);
    
13.             }
    
14.             dp[to] = Math.max(dp[to], to - from + 1 + before);
    
15.             max = Math.max(dp[to], max);
    
16.         }
    
17.         return max * 100;
    
18.     }
    
19. 
    
20.     public static void main(String[] args) {
    
21.         int[][] intervals = new int[][]{{1, 5}, {3, 7}, {6, 8}};
    
22.         System.out.println(MaxIncome.solution(intervals));
    
23.     }
    
24. }

复制代码

按照楼上的思路写了一个...

的萨菲 发表于 2019-5-17 13:33
和meeting room有什么区别吗？应该就是只有一个房间然后尽可能多的安排meeting吧。我想的是按照start 排序 ...

这个不行, 这个方法就是贪心, 等于选择当前的meeting, 否决下一个meeting. 例如 1-3, 2-100, 4-5 会得出1-3, 4-5这个组合

x1111 发表于 2019-5-17 12:35
对所有的reversation每天都是100？还是不同的给不同的价格

价格都是一样的：1天100