Find the positions that matches a condition on parent and child lists-CodePudding

Given a parent list with start and end times as numbers say (p1, p2):

1,5
2,2
4,10

Also another child list with their start and end times as (c1, c2):

2, 4
15,20

Find the index position from the parent and child list such that the below condition is satisfied:

p1 <= c1 <= c2 <= p2

For this example, the expected result is (0,0).

Explanation:

The valid combination is :

1 <= 2 <= 4 <= 5 that is position 0 from the parent list (1,5) matches with the condition for position 0 (2,4) of the child list.

So position 0 from the parent list and position 0 from the child list that is (0,0)

Constraints:

size of the parent and child list can be from 1 to 10^5
each element of this list can be from 1 to 10^9

Code that I tried:

static List<List<Integer>> process(List<List<Integer>> parent, List<List<Integer>> child) {
    List<List<Integer>> answer = new ArrayList<>();
    for(int i=0; i<parent.size(); i  ) {
        List<Integer> p = parent.get(i);
        int p1 = p.get(0);
        int p2 = p.get(1);
        for(int j=0; j<child.size(); j  ) {
            List<Integer> c = child.get(j);
            int c1 = c.get(0);
            int c2 = c.get(1);
            if((p1 <= c1) && (c1 <= c2) && (c2 <= p2)) {
                answer.add(Arrays.asList(i, j));
            }
        }
    }
    return answer;
}

This code works for small inputs but fails for larger list sizes with time-out errors. What is the best approach to solve this problem?

CodePudding user response：

I recommend that you sort the two lists. Go through list 1 and do a binary search on search 2 to find the first pair that satisfies this condition.

Note that you can discard some elements before sorting the list. If the second element is greater than the first, you can discard it.

CodePudding user response：

Lets consider each interval as an event. One idea would be to sort the parent and child list and then scan them from left to right. While doing this, we keep track of the "active events" from the parent list. For example, if the parent list has events e1 = (1, 5), e2 = (8, 11) and the child list has events e1' = (2, 6), e2' = (9, 10), a scan would look like this: start event e1 -> start event e1' -> end event e1 -> end event e1' -> start event e2 -> start event e2' -> end event e2' -> end event e2. While scanning, we keep track of the active events from the parent list by adding them to binary search tree, sorted by starting point. When we end an event ek' from the child list, we search for the starting point of ek' in the binary tree. If there exists a smaller key, we have found our two events. The total time complexity is O(n*log(n)), since we need to sort our two arrays to be able to scan the intervals. Also, adding events to our binary search tree costs only O(log(n)) time, so while scanning, the algorithmic complexity doesn't decrease. I got part of the idea from here, so looking at this might help you to understand, what i am doing: Sub O(n^2) algorithm for counting nested intervals?