Python में इमारतों की अधिकतम ऊंचाई ज्ञात करें

n इमारतें एक पंक्ति में (1 से n लेबल)। प्रतिबंध: restrictions[i] = (id, max_height)। नियम: ऊंचाई ≥ 0, पहली इमारत की ऊंचाई = 0, आसन्न इमारतों में ऊंचाई अंतर ≤ 1। अधिकतम संभव ऊंचाई खोजें।

एल्गोरिदम: दो पास + शिखर गणना

1. प्रतिबंधों को id द्वारा सॉर्ट करें
2. फॉरवर्ड पास: बाएं से दाएं, प्रत्येक प्रतिबंध को पिछले से अधिकतम संभव तक सीमित करें
3. बैकवर्ड पास: दाएं से बाएं, प्रत्येक प्रतिबंध को अगले से अधिकतम संभव तक सीमित करें
4. शिखर गणना: प्रत्येक आसन्न प्रतिबंध जोड़ी के बीच, अधिकतम संभव शिखर ऊंचाई = (dist + h1 + h2) // 2
5. अंतिम खंड (अंतिम प्रतिबंध से n तक) भी जांचें

Python कार्यान्वयन

def max_building_height(n, restrictions):
    if not restrictions:
        return n - 1  # 0, 1, 2, ..., n-1
    
    # id द्वारा सॉर्ट
    restrictions = sorted(restrictions, key=lambda x: x[0])
    
    # फॉरवर्ड पास: बाएं से दाएं प्रसार
    k = 0  # पिछली ऊंचाई
    idx = 1  # पिछला id (पहली इमारत id=1, height=0)
    for r in restrictions:
        r[1] = min(r[1], k + r[0] - idx)
        k = r[1]
        idx = r[0]
    
    # बैकवर्ड पास: दाएं से बाएं प्रसार
    k = restrictions[-1][1]
    idx = restrictions[-1][0]
    restrictions.reverse()
    for r in restrictions[1:]:  # अंतिम (अब पहला) छोड़ें
        r[1] = min(r[1], k - r[0] + idx)
        k = r[1]
        idx = r[0]
    restrictions.reverse()
    
    # शिखर गणना
    f = 0  # पिछली वास्तविक ऊंचाई
    idx = 1
    res = 0
    for r in restrictions:
        # इस प्रतिबंध पर वास्तविक ऊंचाई (पिछले से सीमित)
        ff = min(f + r[0] - idx, r[1])
        # दो प्रतिबंधों के बीच अधिकतम शिखर
        peak = (r[0] - idx + f + ff) // 2
        res = max(res, peak)
        idx = r[0]
        f = ff
    
    # अंतिम खंड: अंतिम प्रतिबंध से n तक
    res = max(res, f + n - idx)
    return res

# परीक्षण
n = 5
restrictions = [[2, 1], [4, 3]]
print(max_building_height(n, restrictions))  # 4

व्याख्या (n=5, restrictions=[[2,1],[4,3]])

1. सॉर्ट: [[2,1], [4,3]]
2. फॉरवर्ड: id=2 पर max=min(1, 0+2-1)=1; id=4 पर max=min(3, 1+4-2)=3
3. बैकवर्ड: id=4 पर 3; id=2 पर min(1, 3-2+4)=1 (कोई बदलाव नहीं)
4. शिखर गणना:
   • id=1(0) से id=2(1): dist=1, peak=(1+0+1)//2=1
   • id=2(1) से id=4(3): dist=2, peak=(2+1+3)//2=3
   • id=4(3) से n=5: 3+5-4=4
5. अधिकतम = 4

संभावित ऊंचाई अनुक्रम

[0, 1, 2, 3, 4] - इमारत 2 पर ऊंचाई 1, इमारत 4 पर ऊंचाई 3, अधिकतम 4 (इमारत 5 पर)

जटिलता

• समय: O(r log r) जहां r = प्रतिबंधों की संख्या (सॉर्टिंग)
• स्थान: O(r)