Google - 1

Question

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

Complexity

• time complexity: O(NlgN)
  • sort: O(NlgN)
  • find: O(lgN)
  • loops: O(N)
• space complexity: O(N)
  • space of output list

Code

/**
 * 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<Integer> findNum(List<Interval> intervals, int[] nums) {
    List<Integer> result = new ArrayList<Integer>();
    if (nums == null || intervals == null) {        
        return result;
    }
    for (int num: nums) {
        if (checkInterval(intervals, num)) {
            result.add(num);
        }
    }
    return result;
}
private boolean checkInterval(List<Interval> 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;
    }
}