s*********p
发帖数: 130 | 1 一道FB家面试题，不是很理解
Given n intervals [si, fi], find the maximum number of overlapping intervals
.
比如如果是 [1, 2] [2, 10], [3,4], 按照Leetcode 那道merge interval 的思路的解
法就应该结果是3， 因为 [1,2] [3,4] 都与[2,10] overlap. 这是我写的代码：
public class Solution {
public int maxIntervals(List intervals) {
if (intervals == null || intervals.size() == 0) {
return 0;
}
if (intervals.size() == 1) {
return 1;
}
int count = 1;
int max = 1;
// Sort the intervals based on start
Collections.sort(intervals, new IntervalComparator());
Interval prev = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.start <= prev.end) {
int left = Math.min(curr.start, prev.start);
int right = Math.max(curr.end, prev.end);
prev = new Interval(left, right);
count++;
max = Math.max(count, max);
} else {
prev = curr;
count = 1;
}
}
return max;
}
private class IntervalComparator implements Comparator {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
}
但是，另外一个解释是答案应该为2, 因为 [1,2] [3,4] 其实并不overlap.
版上有人见过这个题吗？到底应该怎么理解呢？ | y******0
发帖数: 93 | 2 做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。
这个题目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。
所以[1，2]和[3，4]在这个意义上说就不是overlap了。
当然你可以和面试官double check。
intervals
【在 s*********p 的大作中提到】
: 一道FB家面试题，不是很理解
: Given n intervals [si, fi], find the maximum number of overlapping intervals
: .
: 比如如果是 [1, 2] [2, 10], [3,4], 按照Leetcode 那道merge interval 的思路的解
: 法就应该结果是3， 因为 [1,2] [3,4] 都与[2,10] overlap. 这是我写的代码：
: public class Solution {
: public int maxIntervals(List intervals) {
: if (intervals == null || intervals.size() == 0) {
: return 0;
: }
| s*********p
发帖数: 130 | 3 多谢大牛的指点，小弟学习了！！
大牛能不能给个思路这题怎么做
做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。这个题
目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。所以[1，2]和[3，4]
在这个意义上说就........
【在 y******0 的大作中提到】
: 做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。
: 这个题目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。
: 所以[1，2]和[3，4]在这个意义上说就不是overlap了。
: 当然你可以和面试官double check。
:
: intervals
| l****i
发帖数: 2772 | 4 这题和“一堆会议的start和end，问最少需要多少会议室”，一样。所有时间排序到一
起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是解。
4]
【在 s*********p 的大作中提到】
: 多谢大牛的指点，小弟学习了！！
: 大牛能不能给个思路这题怎么做
:
: 做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。这个题
: 目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。所以[1，2]和[3，4]
: 在这个意义上说就........
| y******0
发帖数: 93 | 5 是的，只要几行代码:
【在 l****i 的大作中提到】
: 这题和“一堆会议的start和end，问最少需要多少会议室”，一样。所有时间排序到一
: 起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是解。
:
: 4]
| q*****l
发帖数: 124 | 6 还有道类似的题
Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum ?
貌似用DP可解 | s*********p
发帖数: 130 | 7 一道FB家面试题，不是很理解
Given n intervals [si, fi], find the maximum number of overlapping intervals
.
比如如果是 [1, 2] [2, 10], [3,4], 按照Leetcode 那道merge interval 的思路的解
法就应该结果是3， 因为 [1,2] [3,4] 都与[2,10] overlap. 这是我写的代码：
public class Solution {
public int maxIntervals(List intervals) {
if (intervals == null || intervals.size() == 0) {
return 0;
}
if (intervals.size() == 1) {
return 1;
}
int count = 1;
int max = 1;
// Sort the intervals based on start
Collections.sort(intervals, new IntervalComparator());
Interval prev = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.start <= prev.end) {
int left = Math.min(curr.start, prev.start);
int right = Math.max(curr.end, prev.end);
prev = new Interval(left, right);
count++;
max = Math.max(count, max);
} else {
prev = curr;
count = 1;
}
}
return max;
}
private class IntervalComparator implements Comparator {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
}
但是，另外一个解释是答案应该为2, 因为 [1,2] [3,4] 其实并不overlap.
版上有人见过这个题吗？到底应该怎么理解呢？ | y******0
发帖数: 93 | 8 做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。
这个题目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。
所以[1，2]和[3，4]在这个意义上说就不是overlap了。
当然你可以和面试官double check。
intervals
【在 s*********p 的大作中提到】
: 一道FB家面试题，不是很理解
: Given n intervals [si, fi], find the maximum number of overlapping intervals
: .
: 比如如果是 [1, 2] [2, 10], [3,4], 按照Leetcode 那道merge interval 的思路的解
: 法就应该结果是3， 因为 [1,2] [3,4] 都与[2,10] overlap. 这是我写的代码：
: public class Solution {
: public int maxIntervals(List intervals) {
: if (intervals == null || intervals.size() == 0) {
: return 0;
: }
| s*********p
发帖数: 130 | 9 多谢大牛的指点，小弟学习了！！
大牛能不能给个思路这题怎么做
做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。这个题
目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。所以[1，2]和[3，4]
在这个意义上说就........
【在 y******0 的大作中提到】
: 做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。
: 这个题目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。
: 所以[1，2]和[3，4]在这个意义上说就不是overlap了。
: 当然你可以和面试官double check。
:
: intervals
| l****i
发帖数: 2772 | 10 这题和“一堆会议的start和end，问最少需要多少会议室”，一样。所有时间排序到一
起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是解。
4]
【在 s*********p 的大作中提到】
: 多谢大牛的指点，小弟学习了！！
: 大牛能不能给个思路这题怎么做
:
: 做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。这个题
: 目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。所以[1，2]和[3，4]
: 在这个意义上说就........
| | | y******0
发帖数: 93 | 11 是的，只要几行代码:
【在 l****i 的大作中提到】
: 这题和“一堆会议的start和end，问最少需要多少会议室”，一样。所有时间排序到一
: 起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是解。
:
: 4]
| q*****l
发帖数: 124 | 12 还有道类似的题
Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum ?
貌似用DP可解 | s*********p
发帖数: 130 | 13
这题这么写可以吗？
分别把start array and end array排序，然后线性向下扫。
但是加入输入不把start 和 end 分开，而是向leetcode 那样建一个Interval class,
怎么保证start 和 end都有序呢？
public class Solution {
public int numOverLaps(List start, List end) {
if (start == null || start.size() == 0 || end == null || end.size()
== 0) {
return 0;
}
if (start.size() != end.size()) {
return 0;
}
Collections.sort(start);
Collections.sort(end);
int startP = 0;
int endP = 0;
int numActive = 0;
int numOverlap = 0;
while (startP < start.size() && endP < end.size()) {
if (start.get(startP) < end.get(endP)) {
numActive++;
numOverlap = Math.max(numOverlap, numActive);
startP++;
} else {
numActive--;
endP++;
}
}
return numOverlap;
}
public static void main(String[] args) {
Solution sol = new Solution();
List start = new ArrayList();
List end = new ArrayList();
start.add(1);
start.add(2);
start.add(5);
start.add(4);
end.add(3);
end.add(4);
end.add(6);
end.add(7);
int result = sol.numOverLaps(start, end);
System.out.println("Result is " + result);
}
}
【在 l****i 的大作中提到】
: 这题和“一堆会议的start和end，问最少需要多少会议室”，一样。所有时间排序到一
: 起，线性走一遍，遇到start +1，end -1. 走的过程中得最大值就是解。
:
: 4]
| f***b
发帖数: 21 | 14 看来是常见题啊
板上之前看过一个题也是这个
Given a array of pairs where each pair contains the start and
end time of a meeting (as in int),
Determine if a single person can attend all the meetings
Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
Output: false
Follow up:
determine the minimum number of meeting rooms needed to hold all the
meetings.
Input array(pair(1, 4), pair(2,3), pair(3,4), pair(4,5))
Output: 2 | f**********t
发帖数: 1001 | 15 int needRooms(vector> &meetings) {
struct Cmp {
bool operator()(const tuple &x, const tuple &y) {
return get<0>(x) < get<0>(y);
}
};
vector> vt;
for (auto meeting : meetings) {
vt.push_back(make_tuple(get<0>(meeting), true));
vt.push_back(make_tuple(get<1>(meeting), false));
}
sort(vt.begin(), vt.end(), Cmp());
int res = 0;
int pretime = -1;
int start = 0;
int end = 0;
int rooms = 0;
for (auto t : vt) {
if (pretime != get<0>(t)) {
rooms += start - end;
res = max(res, rooms);
start = 0;
end = 0;
pretime = get<0>(t);
}
if (get<1>(t) == true) {
++start;
} else {
++end;
}
}
rooms += start - end;
res = max(res, rooms);
return res;
} | d****n
发帖数: 233 | 16 A similar problem :
http://www.geeksforgeeks.org/minimum-number-platforms-required-
【在 y******0 的大作中提到】
: 做题的时候，不光要想题，还要想找个题和现实生活中的实际问题有什么意义。
: 这个题目的现实意义是如果有一堆会议让你安排，最少需要多少会议室。
: 所以[1，2]和[3，4]在这个意义上说就不是overlap了。
: 当然你可以和面试官double check。
:
: intervals
|
|
