选斑竹，对对子吧？ (转载)# Joke - 肚皮舞运动
s*p
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.
版上有人见过这个题吗？到底应该怎么理解呢？
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
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.
版上有人见过这个题吗？到底应该怎么理解呢？
