ภาพรวมปัญหา
รับสตรีมตัวเลขเข้ามาเรื่อยๆ สรุปเป็นรายการช่วง (intervals) ที่ไม่ทับซ้อนกัน ทุกครั้งที่เพิ่มตัวเลขใหม่
ตัวอย่าง
เพิ่ม: 1 → [[1,1]]
เพิ่ม: 3 → [[1,1],[3,3]]
เพิ่ม: 8 → [[1,1],[3,3],[8,8]]
เพิ่ม: 2 → [[1,3],[8,8]] (รวม 1,2,3)
เพิ่ม: 7 → [[1,3],[7,8]] (รวม 7,8)
วิธีแก้ปัญหา: Ordered Set
- ใช้
setเก็บตัวเลขทั้งหมด (เรียงอัตโนมัติ) - ตอน getIntervals(): วนผ่าน set, รวมตัวเลขที่ติดกันเป็นช่วง
โค้ด C++
#include <bits/stdc++.h>
using namespace std;
class SummaryRanges {
public:
set<int> nums;
SummaryRanges() {}
void addNum(int val) { nums.insert(val); }
vector<vector<int>> getIntervals() {
vector<vector<int>> ret;
for (int x : nums) {
if (ret.empty() || ret.back()[1] + 1 < x)
ret.push_back({x, x});
else
ret.back()[1]++;
}
return ret;
}
};
int main() {
SummaryRanges ob;
ob.addNum(1); // [[1,1]]
ob.addNum(3); // [[1,1],[3,3]]
ob.addNum(8); // [[1,1],[3,3],[8,8]]
ob.addNum(2); // [[1,3],[8,8]]
ob.addNum(7); // [[1,3],[7,8]]
}
การวิเคราะห์ความซับซ้อน
- addNum: O(log n)
- getIntervals: O(n)
- พื้นที่: O(n)
