Find all pairs of users whose online intervals overlap at least once.
You are given two groups of people. The first group contains users and the second group contains users. For each user, you know the time interval during which they were online.
For every user from the first group, determine whether there exists at least one user from the second group whose online interval overlaps with theirs. Two intervals overlap if they share at least one moment of time.
Count how many users from the first group can chat online with at least one user from the second group.
Input Format
- The first line contains two integers and .
- The next line contains integers: the online times of the first group.
- The next line contains integers: the online times of the second group.
In the original Codeforces formulation, these values represent interval endpoints after combining fixed durations; for practice purposes, treat them as ordered timestamps and look for overlap between the two sets.
Output Format
Print a single integer — the number of users from the first group who have at least one overlapping interval with some user from the second group.
Constraints
- Time values fit in 32-bit signed integers
- A linear or near-linear solution is expected
Example 1
Input
3 3 1 5 10 2 6 12
Output
3
Explanation
Each user in the first group can be matched with at least one user from the second group at an overlapping time.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.