Friday, January 29, 2021

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.

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):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * 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):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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;
    }
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)