Lintcode 821. Time Intersection

Give two users' ordered online time series, and each section records the user's login time point x and offline time point y. Find out the time periods when both users are online at the same time, and output in ascending order.

Example

Example 1:

Input: seqA = [(1,2),(5,100)], seqB = [(1,6)]
Output: [(1,2),(5,6)]
Explanation: In these two time periods (1,2), (5,6), both users are online at the same time.

Example 2:

Input: seqA = [(1,2),(10,15)], seqB = [(3,5),(7,9)]
Output: []
Explanation: There is no time period, both users are online at the same time.

Notice

• We guarantee that the length of online time series meet 1 <= len <= 1e6.
• For a user's online time series, any two of its sections do not intersect.

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 seqA: the list of intervals
     * @param seqB: the list of intervals
     * @return: the time periods
     */
    public List<Interval> timeIntersection(List<Interval> seqA, List<Interval> seqB) {
        List<Interval> ans = new ArrayList<>();
        if (seqA == null || seqA.size() == 0 || seqB == null || seqB.size() == 0) {
            return ans;
        }
        
        List<Event> events = new ArrayList<>();
        for (Interval a : seqA) {
            events.add(new Event(a.start, 0));
            events.add(new Event(a.end, 1));
        }
        
        for (Interval b : seqB) {
            events.add(new Event(b.start, 0));
            events.add(new Event(b.end, 1));
        }
        
        Collections.sort(events, new MyEventComparator());
        
        int count = 0;
        for (int i = 0; i < events.size(); i++) {
            Event event = events.get(i);
            if (event.flag == 0) {
                count++;
            } else {
                count--;
            }
            
            if (count == 2) {
                Interval interval = new Interval(event.time, events.get(i + 1).time);
                ans.add(interval);
            }
        }
        
        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 b.flag - a.flag;
    }
}

Update on 1/28/2021:

Since the two lists are sorted, we don't need to sort them again. We can merge the two lists like merging two sorted arrays. If there are intersection, we get the intersection and add to the result list. In the end, we compare the end boundary and move the smaller one.

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 seqA: the list of intervals
     * @param seqB: the list of intervals
     * @return: the time periods
     */
    public List<Interval> timeIntersection(List<Interval> seqA, List<Interval> seqB) {
        // Write your code here
        List<Interval> ans = new ArrayList<>();
        
        if (seqA == null || seqA.size() == 0 || seqB == null || seqB.size() == 0) {
            return ans;
        }
        
        int i = 0;
        int j = 0;
        
        while (i < seqA.size() && j < seqB.size()) {
            Interval a = seqA.get(i);
            Interval b = seqB.get(j);
            int start = Math.max(a.start, b.start);
            int end = Math.min(a.end, b.end);
            
            if (start < end) {
                ans.add(new Interval(start, end));
            }
            
            if (a.end < b.end) {
                i++;
            } else {
                j++;
            }
        }
        
        return ans;
    }
}