Saturday, October 8, 2011

Finding total possible cable connections between buildings, given their height (Java)

/*The Problem : A cable TV operator is trying to save money by running cables
directly at roof level between pairs of buildings on the same side of the street.
A cable can be connected between the rooftops of two buildings A and B
if no building between them is strictly taller than either A or B.

For instance, suppose there are ?ve buildings on the street with the following heights
(in feet): 160, 145, 153, 170, 180. Let us label the ?ve buildings A, B, C, D and E. In
this case, six pairs of buildings can be connected by a TV cable at roof level: (A,B),
(C,D), (A,C), (B,C), (D,E), (A,D).

In each of the following cases, you are given the heights of the buildings on the street and
you have to compute the number of pairs of buildings that can be directly connected
by a TV cable at roof level. In the example above, the answer is 6.*/

import java.util.*;
class buildingHeightCable
{
public static void main()
{
    System.out.println("Enter the number of buildings");
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int i;
    int h[]=new int[n];
    for(i=0;i<n;i++)
    {
        h[i]=sc.nextInt();
    }
    int j,k=0;
    int f;
    int count=0;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            k=0;
            for(f=i+1;f<j;f++)
            {
                if((h[f]>h[i])||(h[f]>h[j]))
                {
                    k=1;
                }
            }
            if(k==0)
            {
                count++;
                System.out.println(h[i]+"  "+h[j]);
            }
            k=0;
        }
    }
    System.out.println("Total pairs = "+count);
}
}
//Author of program : Mayank Rajoria

No comments:

Post a Comment