Question
【Google|Google - 1】Given an array of integers and a list of intervals with no over overlap between any two intervals, find a list integers from above array, which is in one of interval in above list of intervals
Algorithm
- Sort intervals according their start time in increasing order
- use binary search to check if the integer in one of intervals
- set start point 0 and end point length of list minus 1
- get mid point and check if the integer in midth interval
- if the integer in midth interval, add the integer to output list of integer
- if the integer is less than the start time of midth interval, set end mid - 1
- if the integer is greater than the end time of midth interval, set start mid + 1
- loops until start is greater than end
- time complexity: O(NlgN)
- sort: O(NlgN)
- find: O(lgN)
- loops: O(N)
- space complexity: O(N)
- space of output list
/**
* Definition for an interval.
* public class Interval {
*int start;
*int end;
*Interval() { start = 0;
end = 0;
}
*Interval(int s, int e) { start = s;
end = e;
}
* }
*/
public List findNum(List intervals, int[] nums) {
List result = new ArrayList();
if (nums == null || intervals == null) {
return result;
}
for (int num: nums) {
if (checkInterval(intervals, num)) {
result.add(num);
}
}
return result;
}
private boolean checkInterval(List intervals, int num) {
int start = 0;
int end = intervals.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
int check = checkBelong(intervals.get(mid), num);
if (check == 0) {
return true;
} else if (check == -1) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
private int checkBelong(Interval interval, int num) {
if (num >= interval.start && num <= interval.end) {
return 0;
} else if (num < interval.start) {
return -1;
} else {
return 1;
}
}
