区间最小覆盖

区间最小覆盖:

对于字符串s，给出若干个字符串t，问至少要多少个t，能够将s全部覆盖，t可以重复覆盖s

string s;
struct segment{
    int l, r;
    int id;
    bool operator < (const segment& t) const
    {
        if (l != t.l) return l < t.l;
        return r < t.r;
    }
}seg[N];//存放子区间的id和在s上的左右端点，注意区间需要sort排序
​
//区间覆盖部分
sort(seg + 1, seg + 1 + cnt);//cnt表示子区间的个数
bool flag = false;
int start = 1, ed = s.size();//start在每次找到需要加入的区间时更新
vector<segment> ans;//ans存放结果的l,r,id
for (int i = 1; i <= cnt; i++){
    int j = i, r = -INF;
    int index = -1;
    while (j <= cnt && seg[j].l <= start) {
        if (seg[j].r > r) {
            r = max(r, seg[j].r);
            index = j;
        }
        j++;
    }
    if (r < start) break;
    start = r + 1, i = j - 1;
    ans.push_back({ seg[index].l, seg[index].r,seg[index].id});
    if (r >= ed)
    {
        flag = true;
        break;
    }
}