โจทย์ข้อ Skyline

โจทย์

ความยาก ★★☆☆☆

มีอาคารทั้งหมด $N$ หลัง ($N$ ไม่เกิน 2500) อาคารแต่ละหลังจะมีเริ่มตั้งแต่เมตรที่ $L_i$ ถึงเมตรที่ $R_i$ และมีความสูง $H_i$(ทุกตัวแปรมีค่าในช่วง 1 - 255) หากมองจากทางซ้ายไปขวา (เมตรที่ 1 - 255) สำหรับจุดที่มีความสูงเปลี่ยนไปจากเมตรที่แล้วจะเรียกว่าเส้นขอบฟ้า ถามว่าเส้นขอบฟ้าแต่ละจุดอยู่ที่เมตรที่เท่าไหร่ และมีความสูงเท่าไหร่

โจทย์ข้อ Skyline

https://programming.in.th/tasks/1008

ตัวอย่าง

มีอาคารทั้งหมด 4 หลัง

• (สีส้ม)หลังที่ 1: ตั้งอยู่ที่เมตร 3 ถึง 7 มีความสูง 1

• (สีเขียว)หลังที่ 2: ตั้งอยู่ที่เมตร 5 ถึง 9 มีความสูง 1

• (สีม่วง)หลังที่ 3: ตั้งอยู่ที่เมตร 6 ถึง 8 มีความสูง 2

• (สีฟ้า)หลังที่ 4: ตั้งอยู่ที่เมตร 2 ถึง 3 มีความสูง 3

จะได้เป็นรูปดังนี้

ซึ่งมีเส้นขอบฟ้าทั้งหมด 5 เส้นคือ

1. อยู่ที่เมตรที่ 2 มีความสูง 3
2. อยู่ที่เมตรที่ 3 มีความสูง 1
3. อยู่ที่เมตรที่ 6 มีความสูง 2
4. อยู่ที่เมตรที่ 8 มีความสูง 1
5. อยู่ที่เมตรที่ 9 มีความสูง 0

ข้อมูลนำเข้า

บรรทัดแรก : รับจำนวน $N$ แทนจำนวนอาคารที่ต้องการหาเส้นขอบฟ้า โดยที่ $1\leq N \leq 2500$

บรรทัดที่ 2 ถึง N+1 : บรรทัดที่ i ให้รับค่า $L_i, H_i, R_i$ ระหว่างข้อมูลแต่ละตัวคั่นด้วยเว้นวรรค 1 วรรค แทนเมตรที่เริ่มต้น ความสูง และเมตรที่สิ้นสุดของอาคารลำดับที่ i ตามลำดับ โดยที่ $1\leq L_i, H_i, R_i \leq 255$

ข้อมูลส่งออก

ข้อมูลเส้นขอบฟ้าทุกจุดในรูปแบบ $x_1, h_1, x_2, h_2,...,x_p,h_p$ เมื่อ $p$ คือจำนวนเส้นขอบฟ้า $x_i, h_i$ คือระยะและความสูงของเส้นที่ i และระยะจะเรียงจากน้อยไปมาก

วิเคราะห์โจทย์

ข้อสังเกตอย่างนึงคือ ในแต่ละช่อง(ระหว่างแต่ละเมตร) อาคารที่สูงที่สุดของช่องนั้น จะบังอาคารที่เหลือทั้งหมดอยู่แล้ว

ซึ่งหมายความว่า ขอแค่เรารู้ว่าในแต่ละช่อง อาคารสูงที่สุดเป็นเท่าไหร่ ก็สามารถหาคำตอบได้แล้ว

แปลว่าถ้ามีอาคารใหม่มาก็แค่เอาไปเปรียบเทียบกับอาคารเดิมที่มีอยู่แล้ว ว่าอาคารใหม่นั้นสูงกว่าไหม ถ้าสูงกว่าก็แก้ค่าความสูงของช่องนั้นๆได้เลย

ทีนี้ด้วยความว่าค่าของ $L_i,R_i$ มันน้อยมาก (ค่าไม่เกิน 255) และ มีอาคารแค่ 2500 หลัง ซึ่งก็ถือว่าน้อยเมื่อเทียบกับโจทย์ส่วนใหญ่

ข้อนี้มันก็เลย Brute Force (ทำตรงๆ) ได้ โดยการสร้าง Array มาสักตัวมาเก็บว่าตำแหน่งไหนมีอาคารสูงสุดเท่าไหร่ได้เลย แล้วทุกครั้งที่ได้อาคารใหม่มาก็เอาไปไล่ถามแต่ละช่องเลยว่า

อาคารนี้ไปทับช่องไหนไหม? ไปเรื่อยๆ ก็ได้แล้ว

สมมติว่ามี array ที่เก็บความสูงของอาคารดังนี้

ถ้ามีอาคารใหม่ยาวตั้งแต่ช่อง 3 ถึง 5 แล้วสูง 4:

จริงๆมันก็แค่นั้นแหละ แล้วตอนตอบก็แค่ไล่จากซ้ายไปขวาว่ามีอะไรเปลี่ยนบ้างที่ตำแหน่งไหน

ซึ่งมันก็เขียนง่ายมาก เราก็เลยมาตั้งคำถามใหม่กันว่า…

โจทย์เพิ่มเติม

ถ้ามีอาคารจำนวนมากขึ้นเป็น 100,000 อาคาร และ เมตรเริ่มต้น เมตรสิ้นสุด และความสูงของตึก เป็นค่าได้มากถึง 2000,000,000

โจทย์นี้จะแก้ยังไงดี??

.

.

.

คำใบ้

ถ้าสังเกตนิดนึงคือจุดที่ต้องสนใจจริงๆมีแค่ ตรงขอบอาคารเท่านั้น ไม่จำเป็นต้องสนใจตำแหน่งอื่นๆของอาคารเลย เพราะยังไงความสูงก็ไม่มีการเปลี่ยนแปลงอยู่แล้ว

งั้นตำแหน่งที่ต้องสนใจก็มีแค่ขอบซ้าย/ขวาของอาคารสิ?

เพราะว่าจุดที่สำคัญจริงๆของอาคารมีแค่ขอบซ้าย กับ ขอบขวาเท่านั้น

ทำให้แทนที่จะบอกว่าอาคารสูง $H_i$ จาก $L_i$ ถึง $R_i$ เราสามารถแปลงเป็นสองประโยคได้ว่า

• ที่ตำแหน่ง $L_i$ มีอาคารสูง $H_i$ โผล่ขึ้นมา
• ที่ตำแหน่ง $R_i$ อาคารที่สูง $H_i$ หายไป

ตัวอย่างแปลงประโยค

อาคารเริ่มจากเมตรที่ 2 ถึง 8 และสูง 4:

สรุป

สรุปแล้ว เราต้องเก็บข้อมูลมากสุดแค่ 200,000 ชุดเอง แล้วก็ดูต่อว่า ระหว่างช่วงไหนอาคารสูงที่สุดเท่าไหร่ ก็สามารถหาคำตอบได้แล้ว

โดยวิธีเช็กก็แค่หา Data Structure ที่สามารถหาค่ามากสุดได้ในเวลาน้อย และ support การลบข้อมูลออก เพราะต้องเอาอาคารออกด้วยเมื่อหมดช่วง

ซึ่ง Data Structure ที่เข้าข่ายก็มีพวก

• Set / Multiset
• Priority Queue
• Monotone Stack/ Queue/ Deque
• Fenwick Tree
• Segment Tree

แต่จะใช้อะไรก็ได้แหละ ต่างกันแค่ที่เวลาในการสร้างเท่านั้นเอง