fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4.  
  5. /**
  6.  * <b>IDeserve <br>
  7.  * <a href="https://w...content-available-to-author-only...e.com/c/IDeserve">https://w...content-available-to-author-only...e.com/c/IDeserve</a>
  8.  * The Skyline Problem.
  9.  * @author Nilesh
  10.  */
  11. class SkylineSolution 
  12. {
  13.     private int greater(int a, int b)
  14.     {
  15.         if (a < b) return a;
  16.         return b;
  17.     }
  18.  
  19.     // given two skylines, merge them
  20.     private List<int[]> mergeSkylines(List<int[]> skylineListLower, List<int[]> skylineListHigher)
  21.     {
  22.         int h1 = 20, h2 = 20;
  23.         int newIndex = 0;
  24.         List<int[]> skylineMerged = new ArrayList<int[]>();;
  25.  
  26.         while (true)
  27.         {
  28.             if (skylineListLower.isEmpty() || skylineListHigher.isEmpty())
  29.             {
  30.                 break;
  31.             }
  32.  
  33.             // first key points from both the skylines
  34.             int [] stripe1 = skylineListLower.get(0);
  35.             int [] stripe2 = skylineListHigher.get(0);
  36.  
  37.             // 0: 'x' co-ordinate, 1: height
  38.             int [] mergedStripe = new int[2];
  39.  
  40.             // comparing 'x' co-ordinates of current key points of skyline-1 and skyline-2 
  41.             if (stripe1[0] < stripe2[0]) // key point from skyline-1 is chosen 
  42.             {
  43.                 mergedStripe[0] = stripe1[0];
  44.                 mergedStripe[1] = stripe1[1];
  45.  
  46.                 // if 'y' co-ordinate for key point from skyline-1 is less than last seen height of skyline-2
  47.                 // then we need to update merged key point's 'y' co-ordinate to last seen height of skyline-2
  48.                 if (stripe1[1] < h2)
  49.                 {
  50.                     mergedStripe[1] = h2;
  51.                 }
  52.  
  53.                 // update the last seen height for skyline-1
  54.                 // note that last seen height for skyline-2 is not updated 
  55.                 h1 = stripe1[1];
  56.  
  57.                 // move to next key point for this skyline
  58.                 skylineListLower.remove(0);
  59.             }
  60.             else if (stripe2[0] < stripe1[0])
  61.             {
  62.                 mergedStripe[0] = stripe2[0];
  63.                 mergedStripe[1] = stripe2[1];
  64.  
  65.                 if (stripe2[1] < h1)
  66.                 {
  67.                     mergedStripe[1] = h1;
  68.                 }
  69.  
  70.                 // update the last seen height of skyline-2
  71.                 // note that last seen height of skyline-
  72.                 h2 = stripe2[1];
  73.  
  74.                 skylineListHigher.remove(0);
  75.             }
  76.  
  77.             // if 'x' co-ordinates of key points for both skylines are same
  78.             // then choose the key point with greater 'y' value
  79.             // advance key points for both and hence update last seen height for both
  80.             else
  81.             {
  82.                 mergedStripe[0] = stripe2[0];
  83.                 mergedStripe[1] = greater(stripe1[1], stripe2[1]);
  84.  
  85.                 h1 = stripe1[1];
  86.                 h2 = stripe2[1];
  87.  
  88.                 skylineListLower.remove(0);
  89.                 skylineListHigher.remove(0);
  90.             }
  91.  
  92.             skylineMerged.add(mergedStripe);
  93.         }
  94.  
  95.         if (skylineListLower.isEmpty())
  96.         {
  97.             while (!skylineListHigher.isEmpty())
  98.             {
  99.                 skylineMerged.add(skylineListHigher.remove(0));
  100.             }
  101.         }
  102.         else
  103.         {
  104.             while (!skylineListLower.isEmpty())
  105.             {
  106.                 skylineMerged.add(skylineListLower.remove(0));
  107.             }
  108.         }
  109.  
  110.         // remove redundant key points from merged skyline 
  111.         int current = 0;
  112.         while (current < skylineMerged.size())
  113.         {
  114.             boolean dupeFound = true;
  115.             int i = current + 1;
  116.             while ((i < skylineMerged.size()) &&  dupeFound)
  117.             {
  118.                 if (skylineMerged.get(current)[1] == skylineMerged.get(i)[1])
  119.                 {
  120.                     dupeFound = true;
  121.                     skylineMerged.remove(i);
  122.                 }
  123.                 else
  124.                 {
  125.                     dupeFound = false;
  126.                 }
  127.             }
  128.             current += 1;
  129.         }
  130.  
  131.         return skylineMerged;
  132.     }
  133.  
  134.     private List<int[]> getSkyline(int low, int high, int[][]buildings)
  135.     {
  136.         List<int[]> skyLineList = new ArrayList<int[]>();
  137.  
  138.         // invalid case
  139.         if (low > high)
  140.         {
  141.             return skyLineList;
  142.         }
  143.         // base case: if there is only one building, only two key points define the skyline for it
  144.         else if (low == high)
  145.         {
  146.             int x1 = buildings[low][0];
  147.             int x2 = buildings[low][1];
  148.             int h  = buildings[low][2];
  149.  
  150.             int[] element1 = {x1, h}; // first key point
  151.             int[] element2 = {x2, 0}; // second key point
  152.  
  153.             skyLineList.add(element1);
  154.             skyLineList.add(element2);
  155.  
  156.             return skyLineList;
  157.         }
  158.         // general case
  159.         else
  160.         {
  161.             int mid = (low + high) / 2;
  162.  
  163.             // get the skyline for lower half
  164.             List<int[]> skylineListLower = getSkyline(low, mid, buildings);
  165.  
  166.             // get the skyline for upper half
  167.             List<int[]> skylineListHigher = getSkyline(mid+1, high, buildings); 
  168.  
  169.             // merge skylines for these two halves
  170.             return mergeSkylines(skylineListLower, skylineListHigher);  
  171.         }
  172.     }
  173.  
  174.     public List<int[]> getSkyline(int[][] buildings) 
  175.     {
  176.         return getSkyline(0, buildings.length-1, buildings);
  177.     }
  178.  
  179.     public static void main(String[] args)
  180.     {
  181.         int[][] buildings = { {2,4,3}, {3,6,1}, {3,5,5}, {5,8,2}, {6,10,5}, {7,10,1}, {12, 14, 1}};
  182.  
  183.         SkylineSolution slnForSkyline = new SkylineSolution();
  184.  
  185.         List<int[]> skyLine = slnForSkyline.getSkyline(buildings);
  186.  
  187.         System.out.println("Skyline for given buildings would look like: ");
  188.         for (int i = 0;  i < skyLine.size(); i++)
  189.         {
  190.             System.out.println(skyLine.get(i)[0]+","+skyLine.get(i)[1]);
  191.         }
  192.     }
  193. }
Success #stdin #stdout 0.1s 35924KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Skyline for given buildings would look like: 
2,20
6,0
12,1
14,0
https://ideone.com/yM7ohZ
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!