Points and segments

Question

I am doing an online course and am stuck with this problem.

The first line contains two non-negative integers 1 ≤ n, m ≤ 50,000 - the number of segments and points on the line, respectively. The next n lines contain two integers a_i ≤ b_i defining the ith segment. The next line contains m integers defining the points. All integers have an absolute value of no more than 10 ^ 8. For each segment, print the number of points that it uses from the n -points table.

My decision:

 for point in points: occurrence = 0 for l, r in segments: if l <= point <= r: occurrence += 1 print(occurrence), 

The complexity of this algorithm is O (m * n), which, obviously, is not very efficient. What is the best way to solve this problem? Any help would be appreciated!

Input Example:

 2 3 0 5 7 10 1 6 11 

Output Example:

 1 0 0 

Input Example 2:

 1 3 -10 10 -100 100 0 

Output Example 2:

 0 0 1 

Answer 1

You can use the line sweep algorithm to solve this problem.

First, divide each segment into two points, open and close points.

Add all these points along with these m points and sort them based on their locations.

Iterating over the list of points, maintaining counter , each time you encounter an open point, increase counter , and if you encounter an end point, reduce it. If you encounter a point in the list m , the result for that point is the counter value at the moment.

 For example 2, we have: 1 3 -10 10 -100 100 0 After sorting, what we have is: -100 -10 0 10 100 At point -100, we have `counter = 0` At point -10, this is open point, we increase `counter = 1` At point 0, so result is 1 At point 10, this is close point, we decrease `counter = 0` At point 100, result is 0 So, result for point -100 is 0, point 100 is 0 and point 0 is 1 as expected. 

The time complexity is O ((n + m) log (n + m)) .

Answer 2

[Original answer] how many segments each point is used

I'm not sure I understood the problem correctly, but it looks like a simple example of using a histogram ...

• create an array of counters (one element per point)
• set it to zero

• processes the last line, increasing each used point counter O(m)

• write the answer by reading the histogram O(n)

So the result should be O(m+n) something like (C ++):

 const int n=2,m=3; const int p[n][2]={ {0,5},{7,10} }; const int s[m]={1,6,11}; int i,cnt[n]; for (i=0;i<n;i++) cnt[i]=0; for (i=0;i<m;i++) if ((s[i]>=0)&&(s[i]<n)) cnt[s[i]]++; for (i=0;i<n;i++) cout << cnt[i] << " "; // result: 0 1 

But since you can see that the p[] coordinates are never used, so either I missed something in the description of the problem, or you missed something, or there are only tricks.

[edit1] after resolving inconsistencies in OP, the result is slightly different

By the number of points in each segment:

• create an array of counters (one element per segment)
• set it to zero
• processes the last line, increasing each used point counter O(m)
• write the answer by reading the histogram O(m)

So the result of O(m) is something like (C ++):

 const int n=2,m=3; const int p[n][2]={ {0,5},{7,10} }; const int s[m]={1,6,11}; int i,cnt[m]; for (i=0;i<m;i++) cnt[i]=0; for (i=0;i<m;i++) if ((s[i]>=0)&&(s[i]<n)) cnt[i]++; for (i=0;i<m;i++) cout << cnt[i] << " "; // result: 1,0,0 

[Note]

After adding a new pattern to the OP, it is now clear that:

• indices start at 0
• the problem is how many points from the table p[n] really used by each segment ( m exit numbers)

Answer 3

Use binary search.

Disconnect the line segments according to the 1st value and the second value. If you use c++ , you can use a custom view, for example:

 sort(a,a+n,fun); //a is your array of pair<int,int>, coordinates representing line bool fun(pair<int,int> a, pair<int,int> b){ if(a.first<b.first) return true; if(a.first>b.first) return false; return a.second < b.second; } 

Then, for each point, find the first line that captures the point and the first line that does not (after the line, which of course). If no line captures a point, you can return -1 or something (and not check for a point that does not).

Sort of:

 int checkFirstHold(pair<int,int> a[], int p,int min, int max){ //p is the point while(min < max){ int mid = (min + max)/2; if(a[mid].first <= p && a[mid].second>=p && a[mid-1].first<p && a[mid-1].second<p) //ie, p is in line a[mid] and not in line a[mid-1] return mid; if(a[mid].first <= p && a[mid].second>=p && a[mid-1].first<=p && a[mid-1].second>=p) //ie, p is both in line a[mid] and not in line a[mid-1] max = mid-1; if(a[mid].first < p && a[mid].second<p ) //ie, p is not in line a[mid] min = mid + 1; } return -1; //implying no point holds the line } 

Similarly, write the checkLastHold function.

Then find checkLastHold - checkFirstHold for each point that is the answer.

The complexity of this solution will be O (n log m), since it takes (log m) for each calculation.

Answer 4

Here is my counter solution in Java. Please note that all points, the beginning of the segment and the end of the segment are read into one array.

If points of different PointType have the same x coordinate, then the point is sorted after the beginning of the segment and to the end of the segment. This is done to count the point as “in” the segment, if it coincides with the beginning of the segment (the counter has already been increased) and the end of the segment (the counter has not yet been reduced).

To store the response in the same order as the input points, I create a result array of size pointsCount (only the calculated points, not segments) and sets its element with the index SuperPoint.index , which stores the position of the point in the original input.

 import java.util.Arrays; import java.util.Scanner; public final class PointsAndSegmentsSolution { enum PointType { // in order of sort, so that the point will be counted on both segment start and end coordinates SEGMENT_START, POINT, SEGMENT_END, } static class SuperPoint { final PointType type; final int x; final int index; // -1 (actually does not matter) for segments, index for points public SuperPoint(final PointType type, final int x) { this(type, x, -1); } public SuperPoint(final PointType type, final int x, final int index) { this.type = type; this.x = x; this.index = index; } } private static int[] countSegments(final SuperPoint[] allPoints, final int pointsCount) { Arrays.sort(allPoints, (o1, o2) -> { if (o1.x < o2.x) return -1; if (o1.x > o2.x) return 1; return Integer.compare( o1.type.ordinal(), o2.type.ordinal() ); // points with the same X coordinate by order in PointType enum }); final int[] result = new int[pointsCount]; int counter = 0; for (final SuperPoint superPoint : allPoints) { switch (superPoint.type) { case SEGMENT_START: counter++; break; case SEGMENT_END: counter--; break; case POINT: result[superPoint.index] = counter; break; default: throw new IllegalArgumentException( String.format("Unknown SuperPoint type: %s", superPoint.type) ); } } return result; } public static void main(final String[] args) { final Scanner scanner = new Scanner(System.in); final int segmentsCount = scanner.nextInt(); final int pointsCount = scanner.nextInt(); final SuperPoint[] allPoints = new SuperPoint[(segmentsCount * 2) + pointsCount]; int allPointsIndex = 0; for (int i = 0; i < segmentsCount; i++) { final int start = scanner.nextInt(); final int end = scanner.nextInt(); allPoints[allPointsIndex] = new SuperPoint(PointType.SEGMENT_START, start); allPointsIndex++; allPoints[allPointsIndex] = new SuperPoint(PointType.SEGMENT_END, end); allPointsIndex++; } for (int i = 0; i < pointsCount; i++) { final int x = scanner.nextInt(); allPoints[allPointsIndex] = new SuperPoint(PointType.POINT, x, i); allPointsIndex++; } final int[] pointsSegmentsCounts = countSegments(allPoints, pointsCount); for (final int count : pointsSegmentsCounts) { System.out.print(count + " "); } } }