Given holidays and leaves how to maximize days in vacations - Google Interview

http://www.1point3acres.com/bbs/thread-202732-1-1.html
最大假期问题， 之前面经看到过这个， 但是没有具体的描述， 就放过了。 结果就命背的被考到的。。。。。。。。。。我来详细描述下
input: 
a. 有n个城市， 每个城市之间有飞行时间， 
b. 给个飞行时间，
c. 给个vacation array, 代表每个城市每周的假期
d. 从第一个城市开始
意思就是每个周你可以呆在一个城市， 然后享受那个城市的假期。 
还有个限制， 就是城市与城市之间的飞行时间不能超过给定的飞行时间
求x weeks 你能享受到的最大假期总和你自己设计输入的数据结构

描述起来真他母亲的繁琐， 怪不得没看到详细的说明。 -google 1point3acres
我的大概想法： 
1. 去掉那些飞行时间超过给定飞行时间的边。
2. 用adjancey list做的， 
3. 然后bfs, 暴力求解。 4. 没写完。。。。。。

.1point3acres缃�
如图所示， 最大的应该 
week1, A, sum=2; . From 1point 3acres bbs
week2, B/C, sum=sum+1; 
week3, 回到A, sum+=3
total sum =6 

最后两轮都没回答好， 可以说写出来80%。 估计是挂了。 发现碰到没做过的题， 容易慌， 容易去套已经做过的题。。。， 然后思维混乱， 就会开始朝令夕改。 还是应该不去套已经做过的题， 就从个BF 的方法开始。 我都是想搞个优化， 结果最后又回到最初的暴力。。。。， 郁闷。。。。。。。。。 

4贪心就可以了
4就是把输出string当个栈，如果当前进来的字母比栈顶的小，就把栈顶的扔掉，小的放进去
比如pineapple
p->i->in->ie->a->ap->app->al->ale
擦， 这个不就是那个https://leetcode.com/problems/create-maximum-number/，
其实是新出的remove k digits

5可以dp的

就是
for 第k周
  for 城市c
      计算第k周在城市c的话，前k周最大享受的假期数
for loop里面那个计算可以递归根据第k-1周，城市c'的结果来算

5就是算前x周，假设你最后一周在城市c的话，最多的假期数。

我也有这个疑问, 是不是不能再同一个城市一直呆着
for j = city 0 to city n-1
       for k = city 0 to city n-1 // Flying from city k to city j
如果不能一直在同一个城市戴着, 那么就是 j!=k right?

第五题就是265. Paint House II变形把。。。。再加上飞行时间的限制，以及求min变成了求max。。。。

我也有这个疑问, 是不是不能再同一个城市一直呆着
for j = city 0 to city n-1
       for k = city 0 to city n-1 // Flying from city k to city j
如果不能一直在同一个城市戴着, 那么就是 j!=k right?

第五题就是265. Paint House II变形把。。。。再加上飞行时间的限制，以及求min变成了求max。。。。

最大假期问题，我按照我的理解写了一段测试代码，欢迎评论：

1. class City(object):
2.     def __init__(self, id, dstcity, weekholidays):
3.         self.cityid = id
4.         # key:city_id,value-distance to the destination
5.         self.dstcity = dstcity. more info on 1point3acres.com
6.         # x weeks holidays, index means the number of weeks
7.         self.weekholidays = weekholidays
8. 
   
9. class MaxHoliday(object):
10.     def dfs(self, citys, start_city, week, maxweek, memhash, maxdistance):
11.         if week == maxweek:. from: 1point3acres.com/bbs 
12.             return 0
13.         # if we have searched before, directly return
14.         key = str(week) + '-' + str(start_city.cityid)
15.         if key in memhash:
16.             return memhash[key]
17.         maxdays = 0. more info on 1point3acres.com
18.         for cityid in start_city.dstcity:
19.             if start_city.dstcity[cityid] <= maxdistance:. From 1point 3acres bbs
20.                 maxdays = max(maxdays, self.dfs(citys, citys[cityid], week + 1, maxweek, memhash, maxdistance))
21.         maxdays += start_city.weekholidays[week]
22.         memhash[key] = maxdays. 鍥磋鎴戜滑@1point 3 acres
23.         return maxdays
24. 
    
25.     def maxholidayweeks(self, citys, maxweek, maxdistance):
26.         # key: weeky+cityid,value: maxholiday
27.         memhash = {}
28.         return self.dfs(citys, citys['A'], 0, maxweek, memhash, maxdistance)
29. 
    
30. 
    
31. cityA = City('A', {'B': 6, 'C': 2, 'D': 30}, [2, 0, 3])
32. cityB = City('B', {'A': 6, 'C': 20, 'D': 7}, [1, 1, 0]).鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
33. cityC = City('C', {'A': 2, 'B': 20, 'D': 10}, [1, 1, 1])
34. cityD = City('D', {'A': 20, 'B': 7, 'C': 10}, [0, 0, 2])
35. citys = {'A': cityA, 'B': cityB, 'C': cityC, 'D': cityD}
36. .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
37. T = MaxHoliday(). 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
38. print T.maxholidayweeks(citys, 3, 2)

突然看懂这题了，楼主说是BFS，但其实是DFS把，DFS可以算完一条路径的总时间之后再算另一条路径，比较清晰明了吧，我想问问大致是不是这样
从一个城市开始，这周待在这个城市，算时间，然后DFS到下一个城市，减去飞行时间，剩余的时间和城市的假期小的那个数就是你到下一个城市休假时间，DFS能走的节点数就是题目给的周数，比如说这里就是三周，而且这个DFS可以走已经走过的节点
另外如果飞行距离很长的，比如超过7天的，也就是这一周让你都要在飞机上度过的边基本就不用走了？

这个题飞行时间是不计在假期／工作时间里的，只是用来约束从一个城市能飞到哪些城市。

输入有一个值表示从第k周的城市飞到第k+1周的城市行程不能超过多少小时，因此有的sequence不可行（比如如果两个城市之间太远了，就能直飞，必须有几周在途中的城市先呆着）。

给定城市序列，飞行时间对假期总时间没有影响的。

比如有个假期很多的城市，为了飞到那里必须先飞到某个假期不太多的

algorithm - Given holidays and leaves how to maximize days in vacations? - Stack Overflow
Problem : Given the holidays as list of integers, between 0-364, and number of leaves N available, how to maximize the number of days in X vacations, where a vacation is a date range, which encompasses holidays that falls in the range and uses leaves for the rest in the range.

Method:

1. List all the sub-sequences of holidays.
2. Form all groups of X number of sub-sequences from 1.
3. Filter 2. such that the days-in-between (days of leave) do not exceed N and return them sorted by number of vacation days descending.

Sample output for N=15, X=4:

(17,[[1,15],[53],[150],[245]]) -17 days of vacation, 13 days of leave utilized
                                 for the first vacation 

(14,[[15,20],[53],[185],[359,1]]) -14 days of vacation, 10 days of leave utilized
                                   for the first and last vacation

Read full article from algorithm - Given holidays and leaves how to maximize days in vacations? - Stack Overflow