स्काईलाइन एल्गोरिदम

Question

मैं इस छवि में सिल्हूट के चारों ओर टूटी हुई रेखा के शिखर कैसे पा सकता हूं?

ऊपर के उदाहरण के लिए एक संभावित इनपुट है:

 
WIDTH HEIGHT POSITION 
    3  9  17 
    5  9  9 
12  4  8 
    3  11  3 
10  7  1 
    2  3  19 

तो इस उदाहरण के लिए समाधान

 
[(1, 0), (1, 7), (3, 7), (3, 11), (6, 11), (6, 7), 
(9, 7), (9, 9), (14, 9), (14, 4), (17, 4), (17, 9), 
(20, 9), (20, 3), (21, 3), (21, 0)] 

Answer 1

http://online-judge.uva.es/p/v1/105.html वह जगह है जहाँ मैं मूल रूप से समस्या

देखा और Algorithmist समाधान का एक विवरण दिया गया है: http://www.algorithmist.com/index.php/UVa_105

Answer 2

अनुभवहीन मामले में हो सकता है, यह एक बहुत ही मुश्किल की तरह प्रतीत नहीं होता कलन विधि। क्या आप जानते हैं कि इनपुट आकार बड़ा होगा/कितना बड़ा होगा?

मेरा प्रारंभिक प्रयास: बाएं से दाएं स्थानांतरित करने का प्रयास करें। पहले मूल रेखा पर मौजूद बाएं किनारे के साथ ब्लॉक चुनें। अपने शीर्ष पर चढ़ो। वर्तमान बिंदु और वर्तमान ब्लॉक के ऊपरी दाएं बिंदु के बीच बाएं किनारे वाले सभी ब्लॉक खोजें। उस सेट में, निकटतम चुनें (लेकिन किनारे के मामलों की जांच करें, इरादा इरादा नहीं है)। यदि सेट खाली है, तो ब्लॉक के दाहिने तरफ अपना रास्ता काम करना शुरू करें, अन्य अवरोधों को ढूंढें जिन्हें आप रोक सकते हैं।

असल में यह है कि आप इसे अपनी आंखों से कैसे ढूंढेंगे।

आप सॉर्ट किए गए सूचियों को रखकर और फिर सेट ढूंढने और खोदने के बजाय सूचियों को खोजकर कुछ सरल अनुकूलन कर सकते हैं। उदाहरण के लिए, आप ब्लॉक की 4 क्रमबद्ध सूचियां रख सकते हैं, प्रत्येक पक्ष में से एक के एक्स या वाई समन्वय द्वारा क्रमबद्ध किया जाता है।

यदि आपके पास कई सारे ब्लॉक हैं, तो आप जानकारी को व्यवस्थित करने के लिए बहु-आयामी डेटा संरचना का उपयोग करने पर विचार कर सकते हैं।

Answer 3

यह बहुत सरल है। एक्स अक्ष की लंबाई है जो एक सरणी बनाएं, 0 से शुरू करें। जैसा कि आप इनपुट में पढ़ते हैं, ऊंचाई के अनुसार ऊंचाई को लिखें> = सरणी में उस स्थान पर वर्तमान मान।

फिर सरणी पर लूप करें, और जब भी मूल्य बदलता है तो यह एक चरम है।

असल:

int heights[SIZE] = {0}; 
int i, width, pos, height, prev = -1; 
while (scanf("%d %d %d", &width, &height, &pos) == 3) { 
    for (i = 0; i < width; ++i) { 
     if (heights[pos+i] < height) 
      heights[pos+i] = height; 
    } 
} 

for (i = 0; i < SIZE; ++i) { 
    if (heights[i] != prev) { 
     printf("(%d,%d) ", i+1, heights[i]); 
     prev = heights[i]; 
    } 
} 
printf("\n"); 

Answer 4

मैं कोशिश करते हैं और इस को हल करने के एक जावा वर्ग बनाया है। कक्षा में डेटा सेट बनाने, हल करने और प्रिंट करने के तरीकों को शामिल किया गया है। मैंने बड़े पैमाने पर परीक्षण नहीं किया है, कुछ बग शेष हो सकते हैं। इसके अलावा, मेरा समाधान अनावश्यक रूप से जटिल हो सकता है, लेकिन यह गैर-पृथक ऊंचाई और मानकों को समन्वयित करने के लिए (सिद्धांत रूप में) काम करने के लिए डिज़ाइन किया गया है।

import java.util.Random; 

public class Skyline { 

    private int[][] buildings; 
    private int[][] skyline; 

    private int maxLength; 
    private int maxHeight; 

    public Skyline(int buildings, int maxLength, int maxHeight) { 
     this.maxLength = maxLength; 
     this.maxHeight = maxHeight; 
     makeRandom(buildings); 
    } 

    public Skyline(int[][] buildings, int dimensions) { 
     this.maxLength = maxLength; 
     this.maxHeight = maxHeight; 
     this.buildings = buildings; 
    } 

    public void makeRandom(int buildings) { 
     this.buildings = new int[buildings][3]; 

     Random rand = new Random(); 

     for(int i = 0; i < buildings; i++) { 
      int start = rand.nextInt(maxLength-3); 
      int end = rand.nextInt(maxLength - start - 1) + start + 1; 
      int height = rand.nextInt(maxHeight-1) + 1; 

      this.buildings[i][0] = start; 
      this.buildings[i][1] = height; 
      this.buildings[i][2] = end; 
     } 

     boolean swapped = true; 
     while(swapped) { 
      swapped = false; 
      for(int i = 0; i < this.buildings.length-1; i++) { 
       if(this.buildings[i][0] > this.buildings[i+1][0]) { 
        swapped = true; 
        int[] temp = this.buildings[i]; 
        this.buildings[i] = this.buildings[i+1]; 
        this.buildings[i+1] = temp; 
       } 
      } 
     } 

//  this.buildings[0][0] = 2; 
//  this.buildings[0][1] = 3; 
//  this.buildings[0][2] = 8; 
    } 

    public void printBuildings() { 
     print(this.buildings, false); 
    } 
    public void printSkyline() { 
     print(this.buildings, true); 
    } 

    public void print(int[][] buildings, boolean outline) { 
     char[][] str = new char[this.maxLength][this.maxHeight]; 
     for(int i = 0; i < this.maxLength; i++) { 
      for(int j = 0; j < this.maxHeight; j++) { 
       str[i][j] = '.'; 
      } 
     } 

     for(int i = 0; i < buildings.length; i++) { 
      int start = buildings[i][0]; 
      int height = buildings[i][1]; 
      int end = buildings[i][2]; 

      //print the starting vertical 
      for(int j = 0; j < height; j++) { 
       if(outline) str[start][j] = str[start][j] == '|' ? '.' : '|'; 
       else str[start][j] = '|'; 
      } 

      //print the ending vertical 
      for(int j = 0; j < height; j++) { 
       if(outline) str[end][j] = str[end][j] == '|' ? '.' : '|'; 
       else str[end][j] = '|'; 
      } 

      //print the horizontal 
      if(height > 0) { 
       for(int j = start; j <= end; j++) { 
        str[j][height] = str[j][height] == '|' ? '|' : '-'; 
       } 
      } 

     } 

     for(int i = maxHeight-1; i >= 0; i--) { 
      for(int j = 0; j < maxLength; j++) { 
       System.out.print(str[j][i]); 
      } 
      System.out.println(); 
     } 

     System.out.println(); 
    } 

    public void solveSkyline() { 

     for(int i = 0; i < buildings.length; i++) { 
      boolean reduced = true; 
      while(reduced) { 
       reduced = false; 
       for(int j = i+1; j < buildings.length; j++) { 
        if(buildings[j][0] < buildings[i][2] && buildings[j][1] > buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //if intersecting building is taller, and longer 
         buildings[i][2] = buildings[j][0]; 
         reduced = true; 
         break; 
        } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] <= buildings[i][1] && buildings[j][2] >= buildings[i][2]) { //intersecting building is shorter, but longer 
         buildings[j][0] = buildings[i][2]; 
         reduced = true; 
         break; 
        } else if(buildings[j][0] < buildings[i][2] && buildings[j][1] > 0 && buildings[j][1] < buildings[i][1] && buildings[j][2] <= buildings[i][2]) { //building is invisible, so ignore it 
         buildings[j][1] = 0; 
         reduced = true; 
         break; 
        } else if(buildings[j][0] < buildings[i][2] && buildings[j][2] <= buildings[i][2] && buildings[j][1] > buildings[i][1]) { 
         int[] newBuilding = new int[]{buildings[j][2], buildings[i][1], buildings[i][2]}; 
         int[][] newBuildings = new int[buildings.length+1][3]; 
         boolean inserted = false; 
         buildings[i][2] = buildings[j][0];  
         for(int k = 0; k < buildings.length; k++) { 
          if(inserted == false) { 
           if(newBuilding[0] < buildings[k][0]) { 
            newBuildings[k] = newBuilding; 
            newBuildings[k+1] = buildings[k]; 
            inserted = true; 
           } else { 
            newBuildings[k] = buildings[k]; 
           } 
          } 
          if(inserted == false && k == buildings.length - 1) { 
           newBuildings[k+1] = newBuilding; 
          } else { 
           newBuildings[k+1] = buildings[k]; 
          } 
         } 
         buildings = newBuildings; 
         reduced = true; 
         break; 
        } 
       } 
      } 
     } 
    } 

    public static void main(String args[]) { 
     Skyline s = new Skyline(5, 100, 10); 

     s.printBuildings(); 
     s.solveSkyline(); 
     s.printBuildings(); 

     s.printSkyline(); 
    } 
} 

Answer 5

मैंने स्वीप-लाइन एल्गोरिदम का उपयोग करके इस समस्या को हल किया। यह एक अजगर वर्ग समाधान है।

वहां दो कुंजी: 1) सभी बाएं और दाएं बिंदुओं और उनकी ऊंचाइयों और ऊंचाई के संकेत को बचाने के लिए परिवर्तनीय "अंक" का उपयोग करके इंगित करने के लिए कि अंक बाएं या दाएं हैं या नहीं। 2) परिवर्तनीय "सक्रिय" स्कैन किए गए सभी सक्रिय लाइनों को सहेजने के लिए उपयोग किया जाता है।

वर्ग समाधान: # @param {पूर्णांक [] []} इमारतों # @return {पूर्णांक [] []} डीईएफ़ getSkyline (स्वयं, भवनों): अगर LEN (भवनों) == 0: वापसी [] अगर लेन (भवनों) == 1: लौटने [[इमारतों [0] [0], इमारतों [0] [2]], [इमारतों [0] [1], 0]]

points=[] 
    for building in buildings: 
     points+=[[building[0],building[2]]] 
     points+=[[building[1],-building[2]]] # the negative sign means this point is a right point 
    points=sorted(points, key=lambda x: x[0]) 

    moving, active, res, current=0, [0], [],-1 

    while moving<len(points): 
     i=moving 
     while i<=len(points): 
      if i<len(points) and points[i][0]==points[moving][0]: 
       if points[i][1]>0: 
        active+=[points[i][1]] 
        if points[i][1]>current: 
         current=points[i][1] 
         if len(res)>0 and res[-1][0]==points[i][0]: 
          res[-1][1]=current 
         else: 
          res+=[[points[moving][0], current]] 
       else: 
        active.remove(-points[i][1]) #remove height of the lines than have been finished with scanning 
       i+=1 
      else: 
       break 
     if max(active)<current: 
      current=max(active) 
      res+=[[points[moving][0], current]] 
     moving=i 
    return res 

Answer 6

यहां वर्णित समस्या का मेरा समाधान https://leetcode.com/problems/the-skyline-problem/ यह दो बार इमारतों की सूची को दोहराता है, हालांकि इसे एक ही पुनरावृत्ति में जोड़ा जा सकता है। हालाँकि, और अधिक इष्टतम दृष्टिकोण अगर तुम पर विचार शुद्ध एल्गोरिथ्म समाधान समझाया यहाँ http://www.algorithmist.com/index.php/UVa_105

class Solution { 
public: 
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { 
     // The final result. 
     vector<pair<int, int>> result; 

     // To hold information about the buildings 
     std::set<BuildingInformation> buildingInformation; 

     // Go through each building, and store information about the start and end heights. 
     for (vector<vector<int>>::iterator buildingIt = buildings.begin(); buildingIt != buildings.end(); ++buildingIt) { 
      BuildingInformation buildingStart; 
      buildingStart.x = (*buildingIt)[0]; 
      buildingStart.h = (*buildingIt)[2]; 
      buildingStart.StartOrEnd = Start; 
      buildingInformation.insert(buildingStart); 
      buildingStart.x = (*buildingIt)[1]; 
      buildingStart.StartOrEnd = End; 
      buildingInformation.insert(buildingStart); 
     } 

     // Keep track of the current height. 
     int currentHeight = 0; 

     // A map of active building heights against number of buildings (to handle multiple buildings overlapping with same height). 
     // As it is a map, it'll be sorted by key, which is the height. 
     std::map<int, int> heights; 

     // Go through each building information that we generated earlier. 
     for (std::set<BuildingInformation>::iterator it = buildingInformation.begin(); it != buildingInformation.end(); ++it) { 
      if (it->StartOrEnd == Start) { 
       // This is a start point, do we have this height already in our map? 
       if (heights.find(it->h) != heights.end()) { 
        // Yes, increment count of active buildings with this height/ 
        heights[ it->h ] += 1;  
       } else { 
        // Nope, add this building to our map. 
        heights[ it->h ] = 1; 
       } 

       // Check if building height is taller than current height. 
       if (it->h > currentHeight) { 
        // Update current height and add marker to results. 
        currentHeight = it->h; 
        result.push_back(pair<int, int>(it->x, currentHeight)); 
       } 
      } else { 
       // This is an end point, get iterator into our heights map. 
       std::map<int, int>::iterator heightIt = heights.find(it->h); 

       // Reduce by one. 
       heightIt->second -= 1; 

       // If this was the last building of the current height in the map... 
       if (heightIt->second == 0) { 
        // Remove from heights map. 
        heights.erase(heightIt); 

        // If our height was the current height... 
        if (it->h == currentHeight) { 
         // If we have no more active buildings... 
         if (heights.size() == 0) { 
          // Current height is zero. 
          currentHeight = 0; 
         } else { 
          // Otherwise, get iterator to one past last. 
          heightIt = heights.end(); 

          // Go back to get last valid iterator. 
          --heightIt; 

          // Store current height. 
          currentHeight = heightIt->first; 
         } 

         // Add marker to results. 
         result.push_back(pair<int, int>(it->x, currentHeight)); 
        } 
       } 
      } 
     } 

     return result; 
    } 
private: 
    // Is this a building start or end? 
    enum BuildingStartOrEnd 
    { 
     Start = 0, 
     End 
    }; 

    // Information about building, there are two of these for each building, one for start, one for end. 
    struct BuildingInformation 
    { 
     int x; 
     int h; 
     BuildingStartOrEnd StartOrEnd; 

     // The ordering algorithm for the key, the rules we want to implement is keys are put in X order, and 
     // in the case of a tie (x values the same), we want Start pieces to come before End pieces (this is 
     // to handle cases where an old building ends and a new building begins on same X index, in which case 
     // we want to process the new start before processing the old end), however if we have two Start pieces 
     // at the same index, we wish to favour taller pieces (in this scenario we want to add a marker for the 
     // tallest building), finally if we have two End pieces at the same index, we wish to prefer lower 
     // pieces, as when multiple buildings end, we only want to add one result for the ultimate lowest point. 
     bool operator < (const BuildingInformation & rhs) const 
     { 
      if (x == rhs.x) 
      { 
       if (StartOrEnd == rhs.StartOrEnd) { 
        if (StartOrEnd == Start) 
         return h > rhs.h; 
        else 
         return h < rhs.h; 
       } else { 
        return StartOrEnd < rhs.StartOrEnd; 
       } 
      } 

      return x < rhs.x; 
     } 
    }; 
};