Yelp onsite 面经，跪了一道题

1. /**
   
2. * @param {movies[][]} movies
   
3. * @return {sorted schedule[]}
   
4. */
   
5. var arrangeMovie = function(movies) {
   
6.     if (movies.length === 0) return [];
   
7.     let cache = {};
   
8.     let visitedTime = new Set();
   
9.     for (let i = 0; i < movies.length; i++) {
   
10.             for (let time of movies[i]) {
    
11.                     if (cache[time] === undefined) cache[time] = [];
    
12.                     cache[time].push(i);
    
13.             }
    
14.     }
    
15.     let schedule = [];
    
16.     let visitedMovie = [];
    
17.     visitedMovie.length = movies.length;
    
18.     visitedMovie.fill(0);
    
19.     (function helper(count) {
    
20.             if (count === movies.length) return true;
    
21.             for (let time in cache) {
    
22.                     if (cache.hasOwnProperty(time)) {
    
23.                             if (!visitedTime.has(time)) {
    
24.                                     visitedTime.add(time);
    
25.                                     for (let movie of cache[time]) {
    
26.                                             if (visitedMovie[movie] === 0) {
    
27.                                                     visitedMovie[movie] = 1;
    
28.                                                     schedule.push({
    
29.                                                             "movie": movie,
    
30.                                                             "time": time
    
31.                                                     });
    
32.                                                     if (helper(count+1)) return true;
    
33.                                                     schedule.pop();
    
34.                                                     visitedMovie[movie] = 0;
    
35.                                             }
    
36.                                     }
    
37.                                     visitedTime.delete(time);
    
38.                             }
    
39.                     }
    
40.             }
    
41.             return false;
    
42.     })(0);
    
43.     return schedule;
    
44. };
    
45. let movies = [[14,15,16,17], [14,15,16], [14, 15], [14, 15, 17]];
    
46. console.log(arrangeMovie(movies));

复制代码

GreenIceTea 发表于 2017-1-8 01:35
该解法并不是O(n)吧, 因为你本质上还是backtracking啊. 你提到的"把那个时间点从所有list除去", 其实直接 ...

是O(n), build 一个Map, Key是时间点，value是个movie set

junm5 发表于 2017-10-28 05:08
是O(n), build 一个Map, Key是时间点，value是个movie set

请问能再详细说一下你的解法吗？ 为什么是O(n) ?