CODEWITHSUNDEEP
algorithm
user3758745
user3758745

Reputation: 997

algorithms how to deal with multiple criteria

find 2 rectangles A[i] and A[j] in an array A[n] rectangles such that A[i].width > A[j].width and A[i].length - A[j].length is the longest.

Is there a way to reduce the complexity to O(nlogn)? I can't find a way to get an O(logn) search for the second rectangle. Sorting doesn't seem to help here due to the possibilities of 2 criteria being completely opposite of each other. Maybe I'm just going at it wrong? direct me to the right path please. Thank you.

Note: Homework assignment using different object and using 2 criteria instead of 3, but the context is the same.

Upvotes: 4

Views: 95

Answers (2)

RBarryYoung
RBarryYoung

Reputation: 56745

Since this is homework, here is a high-level answer, with the implementation left as a problem for the OP:

Sort the elements of the array ascending by width. Then scan down the array subtracting the current length from the highest length encountered so far. keep track of the greatest difference encountered so far (and the corresponding i and j). When done you will have the greatest length difference A[i].length-A[j].length where A[i].width > A[j].width

Analysis: sorting the elements takes O(n*Log(n)), all other steps take O(n).

Upvotes: 1

Deepak Singh
Deepak Singh

Reputation: 78

Here is some java code to achieve the same::

  import java.util.Arrays;
  import java.util.Comparator;
  import java.util.Random;

  public class RequiredRectangle {

    public static void main(String[] args) {
        // test the method
        int n=10;
        Rectangle[] input = new Rectangle[n];
        Random r = new Random();
        for(int i=0;i<n;i++){
            input[i] = new Rectangle(r.nextInt(100)+1,r.nextInt(100)+1);
        }

        System.out.println("INPUT:: "+Arrays.deepToString(input));

        Rectangle[] output = getMaxLengthDiffAndGreaterBreadthPair(input);
        System.out.println("OUTPUT:: "+Arrays.deepToString(output));

    }

    public static Rectangle[] getMaxLengthDiffAndGreaterBreadthPair(Rectangle[] input){
        Rectangle[] output = new Rectangle[2];

        Arrays.sort(input, new Comparator<Rectangle>() {
            public int compare(Rectangle rc1,Rectangle rc2){
                return rc1.getBreadth()-rc2.getBreadth();
            }
        });

        int len=0;
        Rectangle obj1,obj2;
        for(int i=0;i<input.length;i++){
            obj2=input[i];
            for(int j=i+1;j<input.length;j++){
                obj1=input[j];
                int temp=obj1.getLength() - obj2.getLength();

                if(temp>len && obj1.getBreadth() > obj2.getBreadth()){
                    len=temp;
                    output[0]=obj1;
                    output[1]=obj2;
                }
            }
        }
        return output;
    }
  }

  class Rectangle{
    private int length;
    private int breadth;

    public int getLength(){
        return length;
    }

    public int getBreadth(){
        return breadth;
    }

    public Rectangle(int length,int breadth){
        this.length=length;
        this.breadth=breadth;
    }

    @Override
    public boolean equals(Object obj){
        Rectangle rect = (Rectangle)obj;

        if(this.length==rect.length && this.breadth==rect.breadth)
            return true;

        return false;
    }

    @Override
    public String toString(){
        return "["+length+","+breadth+"]";
    }
  }

`

Sample Output:

INPUT:: [[8,19], [68,29], [92,14], [1,27], [87,24], [57,42], [45,5], [66,27], [45,28], [29,11]]
OUTPUT:: [[87,24], [8,19]]

Upvotes: 0

Related Questions