Twitter电面

Given a set of [a,b] intervals on the number line, find the longest ordered sequence (consecutive in original order) of (a subset of) the intervals such that each consecutive interval is nested inside the previous one.
"Nested" means this: If interval X is nested inside Y, then Y.a < X.a and X.b < Y.b.
E.g. given [[3,4], [1,9], [2,8], [4,

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

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

Y.a < X.a and X.b < Y.b.
Note: the original order doesn't need to be maintained.
E.g. given [[1,10], [3,4], [4,5], [11,12], [3,8], [2,9]]
Return: [[1,10], [2,9], [3,8], [4,5]]

jiebour 发表于 2016-5-4 02:06
多谢！只是有点繁琐，还是doable的！
再问下楼主，你有先做问卷调查，然后OA，然后再店面之类的嘛？
我 ...

我也是直接电面

tcomein2009 发表于 2016-4-30 23:45
谢楼主！
第三问是不是就是先排序？然后DP？

是的 就比第二问多一个排序

谢楼主！
第三问是不是就是先排序？然后DP？

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

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

楼主，要是只让输出长度的话好说，要输出最后结果的话，感觉有点麻烦。。。求问楼主是怎么解得。。。

jiebour 发表于 2016-5-3 11:55
楼主，要是只让输出长度的话好说，要输出最后结果的话，感觉有点麻烦。。。求问楼主是怎么解得。。。

可以用一个array of array在dp的每一步记下这一步的interval sequence 最后输出最长的interval sequence

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

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

nahgnaw 发表于 2016-5-4 02:49
我也是直接电面

好的多谢！楼主收到onsite了嘛？

jiebour 发表于 2016-5-4 03:11
好的多谢！楼主收到onsite了嘛？

嗯 收到了