15,609,498 members
See more:
Hello. I am attending one course which is about Data Structures and Algorithms. Now I am learning about Divide and Conqure algorithms which are more about recursive functions.

But now in the below practice, I get this error:
```Error Message:
Test 'SolveTest_Q5OrganizingLottery' exceeded execution timeout period.```

Here is the problem description:

```Task. You are given a set of points on a line and a set of segments on a line. The goal is to compute, for each point, the number of segments that contain this point.

Input Format. The first line contains two non-negative integers 𝑠 and 𝑝 defining the number of segments and the number of points on a line, respectively. The next 𝑠 lines contain two integers 𝑎𝑖, 𝑏𝑖 defining the 𝑖-th segment [𝑎𝑖, 𝑏𝑖]. The next line contains 𝑝 integers defining points 𝑥1, 𝑥2, . . . , 𝑥𝑝.

Constraints. 1 ≤ 𝑠, 𝑝 ≤ 50000; −108 ≤ 𝑎𝑖 ≤ 𝑏𝑖 ≤ 108 for all 0 ≤ 𝑖 < 𝑠; −108 ≤ 𝑥𝑗 ≤ 108 for all 0 ≤ 𝑗 < 𝑝.

Output Format. Output 𝑝 non-negative integers 𝑘0, 𝑘1, . . . , 𝑘𝑝−1 where 𝑘𝑖 is the number of segments which
contain 𝑥𝑖. More formally,      𝑘𝑖 = |{𝑗 : 𝑎𝑗 ≤ 𝑥𝑖 ≤ 𝑏𝑗}| .```

For example:

```Sample 1.
Input:
2 3
0 5
7 10
1 6 11
Output:
1 0 0
Here, we have two segments and three points. The first point lies only in the first segment while the remaining two points are outside of all the given segments.```

```Sample 2.
Input:
1 3
-10 10
-100 100 0
Output:
0 0 1```

```Sample 3.
Input:
3 2
0 5
-3 2
7 10
1 6
Output:
2 0```

What I have tried:

My function has to get 3 parameters. The first one is for `starts`, the second one for `ends`, and the third one for `points`.
First I sort both the arrays which are for `starts `and `end `then I define an array which length is equal to the length of `points`. Second in a `for` loop, I define some conditions. I think the first `if` is obvious. but the second and third are used when the element `point[i]` does not exist in the `starts` or `ends` arrays.

Here is my code for `Binary Search`:
C#
```private static long BinarySearch(long[] a, long l, long h, long key)
{
if (h < l)
{
return -1;
}
long mid = (l + h) / 2;
if (key == a[mid])
{
return mid;
}
else if (key < a[mid])
{
return BinarySearch(a, l, mid - 1, key);
}
else
{
return BinarySearch(a, mid + 1, h, key);
}
}```

And this is my main function:
C#
```public static long[] OrganizingLottery(long[] starts,long[] ends, long[] points)
{
long s_length = starts.Length;
long e_length = ends.Length;
Array.Sort(starts);
Array.Sort(ends);
long[] res = new long[points.Count()];
long count = 0;
for (long i = 0; i < points.Length; i++)
{
if (points[i] < starts.Min() || points[i] > ends.Max())
{
count = 0;
continue;
}
long index_in_s = BinarySearch(starts, 0, s_length - 1, points[i]);
long index_in_e = BinarySearch(ends, 0, e_length - 1, points[i]);
if (index_in_s == -1)
{
long s_instead = starts.Where(x => x < points[i]).Max();
index_in_s = BinarySearch(starts, 0, s_length - 1, s_instead);
}
if (index_in_e == -1)
{
long e_instead = ends.Where(y => y > points[i]).Min();
index_in_e = BinarySearch(ends, 0, e_length - 1, e_instead);
}
count = index_in_s - index_in_e + 1;
res[i] = count;
}
return res;
}```

I know that I have used many LINQ functions 😅, but actually I did not have any other idea for solving this problem.
I will be grateful for any help and advice.
Thanks.
Posted
Updated 30-Oct-21 13:46pm
PIEBALDconsult 29-Oct-21 19:16pm
If you want speed:
0) Don't use Linq.
1) There is no reason to use recursion in your BinarySearch method.
Sorry, but we have been told to solve this question using recursion. You are right, it is not good to use Linq, but what should I use instead?
PIEBALDconsult 30-Oct-21 8:23am
Recursion is a very powerful tool which should be used very sparingly.
A binary search is not a good use for recursion. You could also look into tail recursion. It is likely that your instructor said to use recursion as a way for the students to learn when _not_ to use it.

Here is an implementation of a non-recursive generic binary search:
https://www.codeproject.com/Tips/296446/Getting-the-index-of-an-item-in-a-sorted-IList
BillWoodruff 29-Oct-21 21:23pm
An interesting question which i upvoted ... i only upvote class/homework posts that, like yours, show code and substantial work on implementation.

? Check the data for the Samples: they don't seem to be accurate given the description.
Thanks, BillWoodruff. I have checked samples again and I think they are correct. Actually, my code works fine with these samples, but when the number of segments and points become so large no it shows the timeout error to me.

## Solution 1

Yeah, this is a challenge assignment.

Typically, they have the timeout to weed out the "straight forward, brute force" approaches to algorithms.

You cannot make the code you wrote run faster. You have to scrap it and approach the problem entirely differently. Keep in mind, the more `if` and `for/loop` structures you have in your code, the slower it's going to be, so you have to minimize using them.

You are right. I would think more about it.

## Solution 2

My goal here is to teach, not to write code for you, but, to suggest a strategy and show enough code for you to implement that strategy if it meets your requirements. Of course, you can ask questions !

If the final result is simply a count of the number of points in the sample data which are in any of the segments, how about this strategy:

1) get the t0tal span of the segments

2) get the number of points not on the line

3) filter the points so you have only those that are in the line

4) test the filtered points for being in a segment

```private Point Line;

private List<point> Segments = new List<point>()
{
// segment data
};

private List<int> Pts = new List<int>()
{
// point data
};

private int CountPointsOnSegments(List<point> segments, List<int> pts)
{
Line = new Point(segments.Min(p => p.X), segments.Max(p => p.Y));

List<int> ptsnotonline = GetPtsNotOnLine(Line, Pts).ToList();

List<int> ptsonline = Pts.Except(ptsnotonline).ToList();

// ptsonline.Sort(); // sort ?

return = GetPtsOnSegment(Line, Segments, ptsonline).Count();
}

public IEnumerable<int> GetPtsNotOnLine(Point line, List<int> xpts)
{
for (int i = 0; i < xpts.Count; i++)
{
int xloc = xpts[i];

// left for you to write
}
}

public IEnumerable<int> GetPtsOnSegment(Point line, List<point> segments, List<int> xpts)
{
lineX = line.X;

for (int i = 0; i < xpts.Count; i++)
{
int xloc = xpts[i];

for (int j = 0; j < Segments.Count; j++)
{
// left for you to write
}
}
}```

v3