How, using the quick sort algorithm, to determine whether a point lies in an array of segments or not?

Question

Algorithms

Good day to all.
I am taking a course on algorithms and one of the tasks is as follows:
Segments of the form [x, y], where x is the coordinate of the beginning of the segment, and y, respectively, the coordinate of the end, are given. An array of points [x1, x2, x3, ... , xn] is also given. It is necessary to determine how many segments each point contains. The task is in the topic "Quick Sort" and it is obvious that you need to use it, but I do not understand where to start.
The naive algorithm for O(n^2) is clear, for each point we run through all possible segments.
Next, I will give my further reasoning on fastening quick sort:
1. It makes no sense to sort an array of points, since it is necessary to return the result for each point in the order in which it appears in the input stream.
2. It also makes no sense to combine all arrays of segments into one, because then we will not be able to control the beginning and end of the segment, since everything will mix into an ordered mess.
3. Create two arrays for the beginnings and ends of the segments ( 1: [x1, x2, x3, ... , xn], 2: [y1, y2, y3, ... , yn]
Sort them using "quick" sort (using ternary division to speed up sorting of repeating elements) and...
What to do next is not entirely clear to me. how?
I would appreciate any help.

Answer 1

You can also solve in linear time (after sorting):
1) take an array of ends of the segments (xi,1) and (yi,-1), sort (not forgetting that for the same first numbers all the beginnings of the segments go first, and then all the ends : so for the segments [1,2] and [2,3] we get an array (1,1),(2,1),(2,-1),(3,-1))
2) take an array of length n ( number of points), fill it with numbers from 1 to n (if we write in C-like languages, then from 0 to n-1). Sort the array using the condition less(a,b)=(P[a] < P[b]), where P is an array of points. We get point indices sorted by ascending coordinates of corresponding points.
3) We go through both arrays, compare the coordinates. When we pass a point in the array of ends, we add the second element to the counter. When we reach the coordinates of the next point from P, we write the counter value to the result array. Do not forget that the point P[a]=x is processed after all points (x,1) but before all points (x,-1) from the end array.
4) Output an array of results.

Answer 2

Combine together into one array the points of the beginnings (with the additional field "+1") and the ends (with the additional field "-1") of the segments and sort it by the coordinate :
And then go through it once, accumulating the sum of the additional field.