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
:
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:
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.