Is Number of Intersecting Interval Pairs I easy or hard?

It is rated Easy with a 61.2 percent acceptance rate. The brute force idea is immediate, but the counting trick of subtracting disjoint pairs from the total is what separates a fast solution from a slow one. Most candidates solve it in under 30 minutes once they see that trick.

Number of Intersecting Interval Pairs I Python and Java solution?

In Python, sort the starts and ends, then use a while loop with an index into the sorted ends for each start, and subtract the disjoint count from n*(n-1)//2. In Java, use Arrays.sort on two int arrays and a single pointer loop, storing the total in a long to avoid overflow for large n. FleetCode provides both implementations on the solution page.

How to solve Number of Intersecting Interval Pairs I in O(n log n)?

Build arrays of all starts and all ends, and sort both. Total the number of pairs as n*(n-1)/2. For each start, advance a pointer over the sorted ends while the end is strictly less than that start, and add the pointer position to a disjoint count. Subtract the disjoint count from the total to get the number of intersecting pairs.

What is the best approach for Number of Intersecting Interval Pairs I?

The best approach is to count disjoint pairs instead of intersecting pairs, then subtract from the total. Sort the start values and end values separately and use two pointers to count how many intervals end before each start. This runs in O(n log n) time with O(n) extra space.

What data structure is used in Number of Intersecting Interval Pairs I?

The solution uses plain arrays. You store the interval start and end values in two arrays, sort them, and scan them with pointers or binary search. No hash map or tree structure is required.

What is the time complexity of Number of Intersecting Interval Pairs I?

The optimal solution runs in O(n log n) time because sorting the start and end arrays dominates the cost. The two-pointer scan after sorting is O(n). The brute force pair check runs in O(n^2) time.

Is Number of Intersecting Interval Pairs I asked at Google, Amazon, or Meta?

This problem is not confirmed by our tags as asked at a specific company. Its tags are Array, Binary Search, Sorting, and Enumeration, which match common interval and sorting interview questions. Practice it to build the sorting and counting pattern used in many interval problems.

Description Hints 1 Solution Video 10:00

4056. Number of Intersecting Interval Pairs I

Easy61.8% acceptance

You are given a 2D integer array intervals of n elements, where intervals[i] = [start_i, end_i] represents the closed interval from start_i to end_i.

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:

Intervals [1, 2] and [2, 3] intersect at the point 2.
Intervals [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:

The intersection of [1, 5] and [2, 4] is [2, 4].
The intersection of [1, 5] and [3, 6] is [3, 5].
The intersection of [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 <= 100
intervals[i] = [start_i, end_i]
0 <= start_i <= end_i <= 100

Topics

Hints open one at a time

Hint 1

Check every pair of intervals. They intersect exactly when max(start_i, start_j) <= min(end_i, end_j).

10:00

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

4056. Number of Intersecting Interval Pairs I

Topics

Hints open one at a time

Similar problems