题解：

这是一个典型的区间覆盖问题，但是有一个重要特点：当 si > ei 时，表示通宵工作（跨天工作）。我们需要用最少的区间（vaidilutės）覆盖整个一天的时间循环。

关键观察

1. 时间循环处理：由于时间是循环的（一天结束后又是新的一天），我们需要处理跨天的情况。可以将所有区间转换到同一个周期内处理。

2. 区间表示：对于每个 vaidilutė i，她可以工作的区间是 [si, ei]（如果 si ≤ ei）或者 [si, M+ei]（如果 si > ei，表示跨天工作）。

3. 问题转化：我们要求覆盖 [0, M] 这个时间段所需的最少区间数。这是一个经典的最小区间覆盖问题。

4. 贪心算法：对于最小区间覆盖问题，可以使用贪心算法：

   • 从当前覆盖的右端点开始
   • 选择所有左端点 ≤ 当前右端点的区间中，右端点最大的那个
   • 用这个区间的右端点更新当前覆盖范围
   • 重复直到覆盖整个 [0, M]

算法步骤

1. 预处理区间：

   • 如果 si ≤ ei，区间为 [si, ei]
   • 如果 si > ei，区间为 [si, ei+M]（跨天）

2. 扩展区间：由于时间是循环的，我们可以将每个区间复制一份，右端点加上 M，以处理循环特性。

3. 排序：将所有区间按左端点从小到大排序。

4. 贪心选择：

   • 从时间 0 开始
   • 在当前时间点，选择所有左端点 ≤ 当前时间的区间中，右端点最大的
   • 如果无法选择（没有区间可用），返回 -1
   • 用选择的区间更新当前时间
   • 计数加 1
   • 重复直到当前时间 ≥ M

5. 优化：由于 N 最大为 2×10^5，我们需要 O(N log N) 的算法。

复杂度分析

• 排序：O(N log N)
• 贪心扫描：O(N)
• 总复杂度：O(N log N)，可以接受

注意事项

1. 区间长度必须小于 M
2. 当 si > ei 时，区间实际上是跨天的
3. 需要处理循环覆盖，即时间 M 等于时间 0

C语言实现

上面的实现可能会超时，因为我们在每次选择时都扫描了很多区间。我们可以优化贪心过程：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_N 200005

typedef struct {
    long long left;
    long long right;
} Interval;

int compare(const void* a, const void* b) {
    Interval* ia = (Interval*)a;
    Interval* ib = (Interval*)b;
    if (ia->left != ib->left)
        return (ia->left > ib->left) ? 1 : -1;
    return (ia->right > ib->right) ? 1 : -1;
}

int main() {
    int N;
    long long M;
    scanf("%d %lld", &N, &M);
    
    Interval intervals[MAX_N * 2];
    int interval_count = 0;
    
    // 读取并预处理所有区间
    for (int i = 0; i < N; i++) {
        long long s, e;
        scanf("%lld %lld", &s, &e);
        
        if (s < e) {
            intervals[interval_count].left = s;
            intervals[interval_count].right = e;
            interval_count++;
            
            intervals[interval_count].left = s + M;
            intervals[interval_count].right = e + M;
            interval_count++;
        } else {
            intervals[interval_count].left = s;
            intervals[interval_count].right = e + M;
            interval_count++;
            
            intervals[interval_count].left = s + M;
            intervals[interval_count].right = e + 2 * M;
            interval_count++;
        }
    }
    
    // 按左端点排序
    qsort(intervals, interval_count, sizeof(Interval), compare);
    
    // 贪心算法 - 优化版本
    long long current_time = 0;
    long long target = M;
    int count = 0;
    int index = 0;
    
    while (current_time < target) {
        long long max_right = current_time;
        int start_index = index;
        
        // 找到所有左端点 ≤ current_time 的区间中，右端点最大的
        while (index < interval_count && intervals[index].left <= current_time) {
            if (intervals[index].right > max_right) {
                max_right = intervals[index].right;
            }
            index++;
        }
        
        // 如果没有找到可以扩展的区间
        if (max_right == current_time) {
            // 检查是否真的没有区间可用
            if (index == start_index) {
                // 没有左端点 ≤ current_time 的区间
                printf("-1\n");
                return 0;
            }
        }
        
        // 更新当前时间
        current_time = max_right;
        count++;
        
        // 如果已经足够覆盖
        if (current_time >= target) {
            break;
        }
        
        // 如果index没有变化，说明我们需要考虑下一个区间
        if (index < interval_count && intervals[index].left > current_time) {
            // 当前时间点没有区间可以开始，尝试使用下一个区间
            long long next_start = intervals[index].left;
            
            // 检查是否有区间可以跳过这个间隙
            int temp_index = index;
            long long temp_max = current_time;
            
            while (temp_index < interval_count && intervals[temp_index].left <= current_time) {
                if (intervals[temp_index].right > temp_max) {
                    temp_max = intervals[temp_index].right;
                }
                temp_index++;
            }
            
            if (temp_max > current_time) {
                current_time = temp_max;
                count++;
            } else {
                // 无法跳过间隙
                printf("-1\n");
                return 0;
            }
        }
    }
    
    printf("%d\n", count);
    return 0;
}

这个问题的关键在于正确处理时间循环和跨天工作的情况。贪心算法是最优的，因为每次选择能覆盖最远距离的区间不会使结果变差。