Lintcode 1397. Digital Coverage

Description

Given some intervals, ask how many are covered most, if there are multiple, output the smallest number.

• the number of the interval is not more than 10^5.
• the left and right endpoints of the interval are greater than 0 not more than 10^5.

Have you met this question in a real interview?  

Example

Example 1:

 Input:intervals = [(1,7),(2,8)]
 Output:2
Explanation:2 is covered 2 times, and is the number of 2 times the smallest number.

Example 2:

Input:intervals = [(1,3),(2,3),(3,4)]
Output:3 

Explanation:3 is covered 3 times. 

Solution 1:

Split the interval into events and sort by start time. Time complexity O(nlogn)

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        
        List<Event> events = new ArrayList<>();
        for (Interval interval : intervals) {
            events.add(new Event(interval.start, 0));
            events.add(new Event(interval.end, 1));
        }
        
        Collections.sort(events, new MyEventComparator());
        
        int count = 0;
        int ans = 0;
        int maxCount = 0;
        
        for (Event event : events) {
            if (event.flag == 0) {
                count++;
            } else {
                count--;
            }
            
            if (count > maxCount) {
                maxCount = count;
                ans = event.time;
            }
        }
        
        return ans;
    }
}

class Event {
    int time;
    int flag; // 0 start, 1 end
    
    public Event(int time, int flag) {
        this.time = time;
        this.flag = flag;
    }
}

class MyEventComparator implements Comparator<Event> {
    @Override
    public int compare(Event a, Event b) {
        if (a.time != b.time) {
            return a.time - b.time;
        }
        
        return a.flag - b.flag;
    }
}

Solution 2: prefix sum

Allocate an array with size of data range (10^5 for this problem). for each interval, if it's start, count + 1, otherwise count - 1. In the end, we sum up the counts and get the max number.

Time complexity is O(data range)

Code (Java):

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: The intervals
     * @return: The answer
     */
    public int digitalCoverage(List<Interval> intervals) {
        // Write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        
        int[] counts = new int[1000001];
        
        for (Interval interval : intervals) {
            counts[interval.start] += 1;
            counts[interval.end + 1] -= 1;
        }
        
        int maxCount = 0;
        int count = 0;
        int ans = -1;
        
        for (int i = 0; i < counts.length; i++) {
            count += counts[i];
            if (count > maxCount) {
                maxCount = count;
                ans = i;
            }
        }
        
        return ans;
    }
}