Q: In the plane we consider rectangles whose sides are parallel to the coordinate axes and

have positive length. Such a rectangle will be called a box . Two boxes intersect if they have a

common point in their interior or on their boundary.

Find the largest n for which there exist n boxes B1, . . . ,Bn such that Bi and Bj intersect if

and only if i strictly not equal to  j ± 1 (mod n).

A: The condition given by the problem to find the largest n is that Bi and Bj are not adjacent rectangles. Rectangles are called adjacent if their index i in Bi is such that their indexes differ by at most 1.  Moreover, the condition is stated such that non-adjacent rectangles must overlap and have a point common.

In other words the rectangles (B1, B2) , (B2,B3) ... (Bn-1, Bn) (Bn,B1) are adjacent and cannot overlap but any other pairing of Bi can overlap.

Let us take a look at what overlap means. When two rectangles overlap as per the problem description, they have a common point along their projections on the X and the Y-axis
If we take the set of such line segments bounded by the corners of two rectangles along the X-axis  and Y-axis as Ik and Jk respectively where k can vary from 1 to n.
Adjacent rectangles don't intersect. So (Ik, Ik+1) OR (Jk, Jk+1) are disjoint intervals. Then, the possible line segments for adjacent rectangles that are denoted by (I1,I2). . (In-1,In),(In,I1) and (J1, J2), (Jn-1,Jn), ... (Jn,J1) respectively have n pairs of disjoint intervals.
And since non-adjacent rectangles necessarily intersect, their projections on both axes must intersect. How many ever pairs of rectangles we can find that are disjoint on one axes that many can exist on the y-axis as well. Therefore the total number of such pairs will be double the number of disjoint pairs we can find and that will be the largest n to satisfy the condition in the problem.

By writing the line segments as length L1 L2 ..Ln for segment ends (a1,b1) (a2,b2) .. (an,bn), we can choose two points alpha and beta such that alpha is the rightmost among left endpoints and beta is the leftmost among right endpoints.

If alpha is less then beta then all ai is less the alpha is less than beta is less than bi. If every length contains alpha, then there cannot be any disjoint set.
If alpha is greater than beta, then assume Beta = bi  for some i  and alpha = a2 , then we have ai is less than bi or beta which is less than alpha or a2 which is less than b2. This means L2 and Li are disjoint. Now L2 intersects all remaining intervals between L1 and L3 so L2 and Li can be disjoint only if i = 1 or i = 3. Also alpha belongs to the intersection of  each of the remaining intervals which means it is not empty Similarly L5 to Ln,L1 intersect with L3 and consequently they have a non-empty overlap that includes Beta. This leaves only (L1,L2) (L2,L3) and (L1,L3) as the only candidates for the disjoint intervals. And therefore the answer is n = 6.

It was an exercise left out that alpha was claimed to be in the intersection of each of the remaining intervals and that alpha can be assumed to be a2. This is because we choose the leftmost point for alpha.

Write a C program that, given an array A[] of n numbers and another number x, determines whether

or not there exist two elements in S whose sum is exactly x.

int HasTwoNumbersWithSum(int A[], int length, int n)

{

 Qsort(&A, length);
  

For (int I = 0; I < length; i++){

    Assert (a[i] > 0);

    If (A[i] < n && exists(A, length, n- A[i], 0, length – 1 )){

     Return 1;

   }

}

Return 0;

}

Int exists(int A[], int length, int val, int start, int stop)

{

  While (Start <= stop)

 {

Mid = (start + stop )/ 2;

If( A[mid] == val )return 1;

If (start == stop) return 0;

  If ( A[mid] > val)

     Return exists(A, length, start, mid-1);

   Else

     Return exists(A, length, mid+1, stop);

}

Return 0;

}