Problem

Suppose you are given two lists of n points, one list p1, p2, ..., pn on the line y = 0 and the other list q1, q2, ..., qn on the line y = 1. Imagine a set of n line segments connecting each point pi to qi. Write an algorithm to determine how many pairs of the line segments intersect.

Examples

Example 1:

1
2
3

Input: p = [2, 0, 6, 4], q = [0, 5, 1, 4]
Output: 4
Explanation: Look at the diagam above.

Solution

Method 1 - Comparing points

First lets try to think, when the intersection will happen between 2 lines. Look at the cases below:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

  public int numIntersections(List<Integer> p, List<Integer> q) {
    int ans = 0;

    for (int i = 0; i < p.size(); i++) {
      int p1 = p.get(i), q1 = q.get(i);
      for (int j = i + 1; j < segments.size(); j++) {
        int p1 = p.get(j), q1 = q.get(j);
        if ((p1 > p2 && q2 > q1) || (p2 > p1 && q1 > q2)) {
          ans++;
        }
      }
    }

    return ans;
  }

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)