Find the number of rectangles whose length and width are strictly increasing

Question

Problem Statement

I have given N number of rectangles(input from user) whose length and width are taken as an input from user also.

I have to select maximum number of rectangles with a condition that length of first rectangle > length of second rectangle and width of first rectangle > width of second rectangle.

My Procedure

What I am doing is I am sorting each rectangle with respect to length and width, and then considering only those rectangle whose length and width are in increasing order, but my sorting is not working properly.

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct 
{
    int length;
    int width;
}Rectangles;

int compare(const void *first,const void *second)
{
    const Rectangles *rect1 = first;
    const Rectangles *rect2 = second;

    if(rect1->length > rect2->length )
    {
        if(rect1->width > rect2->width)
            return 1;
        else if(rect1->width < rect2->width)
            return -1;
        else 
            return -1;
    }

    else if(rect1->length < rect2->length )
    {
        if(rect1->width < rect2->width)
            return -1;
        else if(rect1->width > rect2->width)
            return -1;
        else 
            return -1;
    }
    else
    {
        if(rect1->width < rect2->width)
            return -1;
        else if(rect1->width > rect2->width)
            return -1;
        else 
            return 0;
    }
}

int main()
{
    int i,nRectangleCount;
    Rectangles stRectangle[MAX];
    printf("Enter total number of rectangles\n");
    scanf("%d",&nRectangleCount);
    printf("Enter %d length and width of rectanle\n",nRectangleCount);
    for(i=0;i<nRectangleCount;++i)
    {
        scanf("%d %d",&stRectangle[i].length,&stRectangle[i].width);
    }

    printf("Before Sorting\n");
    for(i=0;i<nRectangleCount;++i)
    {
        printf("%d %d\n", stRectangle[i].length,stRectangle[i].width);  
    }

    qsort(stRectangle,nRectangleCount,sizeof(Rectangles),compare);

    printf("\n\nAfter Sorting\n");
    for(i=0;i<nRectangleCount;++i)
    {
        printf("%d %d\n", stRectangle[i].length,stRectangle[i].width);  
    }
    return 0;
}

I don't think, it is good idea to solve this question with sorting, I tried to calculate area and then sort it with respect to area, then also it is not working.

Is there any other algorithm to solve this problem.?

Here is the test case:

7
10 12
4 5
15 8
3 18
16 25
1 2
5 10

Answer 1

This is a classical one. Sort your sequence of rectangles by one of the coordinates (for example, by width) and then find a longest increasing subsequence ("LIS") of a sequence of other coordinate. Sorting will take O(nlogn), and finding LIS O(n^2), or O(nlogn) if you use dynamic programming.

Regarding your example, after sorting you will first get a sequence (1,2), (3,18), (4,5), (5,10), (10,12), (15,8), (16,25).

Longest increasing subsequence of a sequence of second coordinates is 2,5,10,12,25 which finally gives (1,2), (4,5), (5,10), (10,12), (16,25). Reversing this sequence gives you a sequence of rectangles that satisfies your condition.

See also:

• Longest increasing subsequence
• How to determine the longest increasing subsequence using dynamic programming?

Answer 2

This problem screams dynamic programming.

Consider if you only had two rectangles, it would trivial, right?

So you core element to work with is a list of valid (increasing, adjacent in input) rectangles, also with the input rectangles.

Base case: Each a list with one rectangle each.

Inductive/Recursive Step: Can we add the successor to any current lists to it (i.e. is for each rectangle list, look at the last rectangle, is the next rectangle in the input valid to add to that list)?

Repeat the Inductive Step until no more rectangles can be added, then just scan your lists for the longest. Apply dynamic programming to keep the complexity down (length N array, indexed by rectangle's position in the input, whose value is the number of elements after it that are valid).

Answer 3

One obivious soultion is this:

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct 
{
    int length;
    int width;
}Rectangles;

int compare(const void *first,const void *second)
{
    const Rectangles *rect1 = (Rectangles*)first;
    const Rectangles *rect2 = (Rectangles*)second;

    if(rect1->length > rect2->length )
    {
        return 1;
    }
    else if(rect1->length == rect2->length )
    {
        if(rect1->width > rect2->width)
            return 1;
    }
    else
        return -1;
}

int main()
{
    int i,j,nRectangleCount;
    Rectangles stRectangle[MAX];
    int rect_count = 5;
    int count = 0;
    stRectangle[0].length = 5;
    stRectangle[0].width = 12;
    stRectangle[1].length = 8;
    stRectangle[1].width = 10;
    stRectangle[2].length = 14;
    stRectangle[2].width = 9;
    stRectangle[3].length = 11;
    stRectangle[3].width = 16;
    stRectangle[4].length = 4;
    stRectangle[4].width = 6;
    qsort(stRectangle, 5, sizeof(Rectangles), compare);
    for(i=0;i<5;i++) {
        for(j=i+1;j<5;j++)
        {
            if(stRectangle[i].length < stRectangle[j].length && stRectangle[i].width < stRectangle[j].width) {
                printf("%d %d > %d %d\n", stRectangle[i].length,stRectangle[i].width,stRectangle[j].length,stRectangle[j].width);
                count++;
            }
        }
    }
    printf("%d",count);
    return 0;
}

I am sure you will find better solutions.

Answer 4

I can think of an O(n**2) solution. Construct a directed graph for all rectangles in the list, where each rectangle corresponds to a vertex. For each rectangle i, examine all other rectangles j and

• if i>j, draw a directed edge from i to j
• if j>i, draw a directed edge from j to i

Once you get the graph, for each vertex without incoming edge, find the longest path starting at that vertex. Then find the overall longest path for the longest paths.

This is O(n**2) time and O(n**2) space.