หากโจทย์ต้องการให้หาค่ามากสุดหรือน้อยสุดที่ทำให้เงื่อนไขเกี่ยวกับค่ามากสุด/น้อยสุดบางอย่างเป็นจริง เทคนิคหนึ่งที่ควรนึกถึงคือการแปลงปัญหาเป็น Decision Problem แล้วทำการ Binary Search

สมมุติให้ "ค่าของความน่าเบื่อของคาบที่เข้าเรียนที่น่าเบื่อมากที่สุด" ที่ยอมรับได้เป็น $a$ นั่นคือ โจทย์ต้องการให้เราหาค่า $a$ ที่สามารถหาวิธีโดดเรียนได้จริง (เรียกว่า $a_{min}$)

สังเกตว่า

• หากทดลองให้ $a = a_0$ แล้วเราสามารถหาวิธีโดดเรียนได้ จะได้ $a_{min} \leq a_0$
• หากทดลองให้ $a = a_0$ แล้วหาวิธีโดดเรียนไม่ได้ จะได้ $a_{min} > a_0$

ดังนั้น เราสามารถหา $a_{min}$ ได้ด้วย Binary Search โดยขอบเขตเริ่มต้นคือ $[x, y]$ เมื่อ $x=$ ค่าที่น้อยสุดในข้อมูลนำเข้า และ $y=$ ค่าที่มากที่สุดในข้อมูลนำเข้า

สมมุติว่าโจทย์ไม่มีเงื่อนไขบังคับว่า "ต้องเข้าเรียนอย่างน้อย 1 คาบในแต่ละวัน" การตรวจสอบว่าสามารถหาวิธีโดดเรียนให้ค่าความน่าเบื่อมากสุดไม่เกิน $a$ ได้จริงหรือไม่ ทำได้ด้วย Greedy Algorithm ดังนี้

• ดูว่าคาบแรกน่าเบื่อเกิน $a$ หรือไม่ ถ้าเกิน เราจะโดดคาบที่ $1$ ถึง $p$ แล้วไปพิจารณาคาบที่ $p+2$ ต่อเลย แต่จะเหลือสิทธิ์โดดเรียนเพียง $k-1$ ครั้ง
• ถ้าคาบแรกไม่เกิน ให้ยอมเรียนไปก่อน แล้วพิจารณาคาบถัดไปแทน หากเจอคาบที่น่าเบื่อเกิน $a$ จึงโดดทีเดียวทั้งหมด $p$ คาบ (หรือจนหมดวันเรียน)
• ทำไปเรื่อย ๆ จนกว่าจะพิจารณาครบทุกคาบ (นั่นคือทำได้) หรือใช้สิทธิ์โดดเรียนเกินที่มีอยู่ (นั่นคือทำไม่ได้)

ถึงอย่างไรก็ตาม หากใส่เงื่อนไข "ต้องเข้าเรียนอย่างน้อย 1 คาบในแต่ละวัน" เข้ามา จะพบว่ามีบางกรณีที่มีปัญหา เช่น หาก $k=1$, $p=5$ และลำดับที่กำหนดให้คือ $3, 2, 1, 2, 3$ คำตอบย่อมเป็น $3$ เสมอ

สามารถแก้ปัญหานี้ได้โดยทดลองเลือกคาบเรียนที่บังคับว่าต้องเรียน 1 คาบ (สมมุติว่าเลือกคาบ $i$ โดยต้องน่าเบื่อไม่เกิน $a$) แล้วหาว่าจำเป็นต้องโดดเรียนในคาบที่ $1$ ถึง $i-1$ กี่ครั้ง (เรียกว่า $l_{i-1}$) และในคาบที่ $i+1$ ถึง $n$ กี่ครั้ง (เรียกว่า $r_{i+1}$) เพื่อไม่ให้มีคาบใดน่าเบื่อเกิน $a$

หากมีค่า $i$ อย่างน้อยหนึ่งค่าที่ทำให้ $l_{i-1}+r_{i+1} \leq k$ แปลว่าเราสามารถหาวิธีโดดเรียนให้ได้ค่าความน่าเบื่อมากสุดไม่เกิน $a$

อนึ่ง $l_i$ และ $r_i$ สามารถหาได้โดยการ precompute ตาม Greedy Algorithm ที่อธิบายข้างต้นจากซ้ายไปขวาและจากขวาไปซ้าย ตามลำดับ

เรา binary search ทั้งหมด $O(\log 10^9)$ ครั้ง แต่ละครั้งต้อง

• precompute $l_i$ และ $r_i$ ใน $O(n)$
• ทดลองเลือกค่า $i=1\dots n$ ที่ทำให้เงื่อนไขเป็นจริงใน $O(n)$

ดังนั้น Time Complexity จึงเป็น $O(n \log 10^9)$