You are given a 2D integer array intervals of n elements, where intervals[i] = [starti, endi] represents the closed interval from starti to endi.
Return the number of pairs of indices (i, j) such that 0 <= i < j < n and intervals[i] and intervals[j] intersect.
Two intervals intersect if they have at least one point in common, including when they only share an endpoint.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4]]
Output: 2
Explanation:
There are 2 intersecting interval pairs:
[1, 2] and [2, 3] intersect at the point 2.[2, 3] and [3, 4] intersect at the point 3.Example 2:
Input: intervals = [[1,5],[2,4],[3,6]]
Output: 3
Explanation:
There are 3 intersecting interval pairs:
[1, 5] and [2, 4] is [2, 4].[1, 5] and [3, 6] is [3, 5].[2, 4] and [3, 6] is [3, 4].Example 3:
Input: intervals = [[1,2],[3,4],[5,6]]
Output: 0
Explanation:
There are no intersecting interval pairs. Hence, the answer is 0.
Constraints:
2 <= n == intervals.length <= 105intervals[i] = [starti, endi]0 <= starti <= endi <= 1091a (Sorting + Binary Search). Sort the intervals by their starting points. For each interval, a later interval intersects it exactly when the later interval's starting point does not exceed the current interval's ending point.
1b (Sorting + Binary Search). Use binary search to find the first later interval whose starting point exceeds the current ending point. Count all intervals between the current interval and that position.
2a (Sweep Line). Create a start event and an end event for each interval. Process events in increasing coordinate order, handling all start events before end events at the same coordinate.
2b (Sweep Line). Maintain the number of active intervals. At each start event, add that number to the answer before activating the new interval. At each end event, deactivate the interval.
[[1,2],[2,3],[3,4]]
[[1,5],[2,4],[3,6]]
[[1,2],[3,4],[5,6]]