Problem statement

https://binarysearch.com/problems/Intersecting-Lines/

Solution

The idea is to find points of intersections of our lines with the left and the right borders. Then we sort them by left coordinate. Now, imagine that we have line i. How to understand if it has intersections with other lines? We need to look at lines 0, ..., i-1 and find the maximum among the right ends: if it is more than the right end of line i, we have intersection. Also we look at lines i+1, ... n-1 and find the minimum of the right ends: if it is less than the right end of line i, we have intersection.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, lines, lo, hi):
        P = sorted([(m*lo + b, m*hi + b) for m, b in lines], key = lambda x: [x[0], -x[1]])
        n, INF, ans = len(P), float("inf"), 0
        B = [x for _, x in P]
        pref = [-INF] + list(accumulate(B, max))
        suff = list(accumulate(B[::-1], min))[::-1] + [INF]

        for i in range(n):
            if pref[i] >= B[i] or suff[i+1] <= B[i]:
                ans += 1

        return ans