运动会

• 计算出每个任务的最迟开始时间（如果开始时间在此之后，那么这个任务肯定做不了了）
• 按照最迟开始时间排序
• 从前向后进行计算，并判断能否做完

def f():
    n=int(input())
    events=[]
    for i in range(n):
        line=[int(item) for item in input().split()]
        events.append(line)
    events=sorted(events,key=lambda x:x[1]-(x[1]-x[0])//2-1)
    start=events[0][0]
    for i in range(n):
        if start>events[i][1]-(events[i][1]-events[i][0])//2-1:
            return -1
        end=start+(events[i][1]-events[i][0])//2+1
        if i==n-1:
            return 1
        start=max(end,events[i+1][0])
    return 1
ans=f()
print(ans)

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
    private int n;
    private int[][] data;
    public static void main(String[] args) {
        Main s = new Main();
        s.input();
        System.out.println(s.solve());
    }
    public void input(){
        Scanner s = new Scanner(System.in);
        this.n = s.nextInt();
        this.data = new int[n][2];
        for (int i = 0; i < n; i++) {
            data[i][0] = s.nextInt();
            data[i][1] = s.nextInt();
        }
        s.close();
    }
    public int solve(){
        Arrays.sort(data, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] != o2[1] ? o1[1] - o2[1]:o1[0] - o2[0];
            }
        });
        int res = 1,begin = data[0][0];
        for (int[] nums : data) {
            if(begin < nums[0])
                begin = nums[0];
            int dura = nums[1] - nums[0];
            int least = dura/2 + 1;
            if(nums[1] - begin >= least){
                begin = begin + least;
            }else return -1;
        }
        return 1;
    }
}

渣渣解法，从头到尾走一遍，时间复杂度用了一个排序+遍历，O(nlogn + n)， 
空间复杂度单纯记录下来输入数据， O(n)

def arrange(events):
        # 按照运动会每个事件的结束时间进行排列，时间复杂度 O(nlogn)
        events.sort(key=lambda tup: tup[1])
        # 模拟从前往后走一遍
        time = 0
        for event in events:
            start, end = event
            # 分别算出最晚要什么时候开始加油 latestStart 和最早开始时间earlistEnd
            cost = (end - start) // 2 + 1
            latestStart = end - cost
            earliestEnd = start + cost
            # 如果在上一个事件完成之后已经超过最晚开始时间，返回-1
            if time > latestStart:
                return -1
            else:
                # 否则直接将时间点推到最早结束时间
                time = earliestEnd
        return 1


while True:
    try:
        n = int(input())
        events = []
        # 将每一组事件作为tuple (start, end) 插入为数组
        for _ in range(n):
            line = input().split()
            x = int(line[0])
            y = int(line[1])
            events.append((x, y))
        # 调用arange函数判断能否完成
        ans = arrange(events)
        print(ans)
    
    except:
        break

#include<iostream>
(720)#include<vector>
#include<algorithm>
using namespace std;
bool cmp(pair<int, int>& p1, pair<int, int>& p2)
{
	if (p1.second < p2.second)
		return true;
	else
		return false;
}
int solution1(vector<pair<int, int>>& vec)
{
	sort(vec.begin(), vec.end(), cmp);
	int pre = vec[0].first;
	for (int i = 0; i < vec.size(); ++i)
	{
		int cur = max(pre, vec[i].first);
		int time = (vec[i].second - vec[i].first) / 2 + 1;
		if (cur + time > vec[i].second)
			return -1;
		pre = cur + time;
	}
	return 1;
}
int main()
{
    
    int n;
    cin>>n;
    vector<pair<int,int>> vec(n);
    for(int i=0;i<n;++i)
        cin>>vec[i].first>>vec[i].second;
    cout<<solution1(vec);
    return 0;
}

#记录[开始时间，最迟开始时间，持续时间]
(5333)#按最迟开始时间排序，最迟开始时间早的一定在晚的前面开始进行
#设置一个时间点
(5334)#（当前时间+加油时间）>下一个最迟开始时间
list = []
N = int(input())
for i in range(N):
    start,end=(int(i) for i in input().split(" "))
    list.append([start,end-(end-start)//2-1,(end-start)//2+1])
list.sort(key=lambda x:x[1])
start=list[0][0]
count=0
for i in list:
    if start>i[1]:
        print(-1)
        break
    else:
        start+=i[2]
        count+=1
if count==N:
    print(1)

#include <vector>
(721)#include <map>
#include <utility>
(1186)#include <iostream>  
#include <algorithm>
using namespace std;
bool cmp(pair<int,int> &a,pair<int,int> &b){
    if((a.second-(a.second-a.first)/2-1)!=(b.second-(b.second-b.first)/2-1))
        return (a.second-(a.second-a.first)/2-1)<(b.second-(b.second-b.first)/2-1);
    else return a.first<b.first;
}
void right(vector<pair<int,int>> table){
    int start=table[0].first;
    int num=table.size();
    for(int i=0;i<num;i++){
        if(start>(table[i].second-((table[i].second-table[i].first)/2+1)))
        {cout<<-1<<endl;
            break;}
        if(i==num-1){
            cout<<1<<endl;
            break;
        }
        int end=start+((table[i].second-table[i].first)/2+1);
        start=max(end,table[i+1].first);
    }
}
int main(){
    int num=0;
    cin>>num;
    vector<pair<int,int>>  table;
    int start,end;
    for(int i=0;i<num;i++){
        cin>>start>>end;
        table.push_back({start,end});
    }
    sort(table.begin(),table.end(),cmp);
    right(table);
    return 0;
}

times = int(input())
tmp = []
for i in range(times):
    l = list(map(int, input().split()))
    tmp.append(l)
tmp.sort(key=(lambda x:x[1]))  # 根据结束时间排序
time = []  (3302)# 计算每个项目的时间
for (s, e) in tmp:
    time.append(int((e - s)//2 + 1))
res = tmp[0][0]
for i in range(len(tmp)):
    if res < tmp[i][1]:
        res += time[i]  # 当前时间加上该项目所需时间
        if res > tmp[i][1]:  (3303)# 如果时间超出项目的结束时间， -1
            print(-1)
            break
    else:
        print(-1)
        break
else:
    print(1)

递归，把开始时间，结束时间列表转化为最早离开时间与最晚到达时间。只要最大的最晚到达时间比最大的最早离开时间大，
则该项目就可以参加。删除这一项之后递归
python解法

def dfs(tlst):
    tlst.sort(key= lambda x:(x[1]),reverse=True)
    print(tlst)
    late_arr=tlst[0][1]
    tlst.pop(0)
    print(tlst)
    if not tlst:
        return 1
    tlst.sort(reverse=True)
    early_lef=tlst[0][0]
    print(late_arr,early_lef)
    print(early_lef>late_arr)
    if early_lef>late_arr:
        print(-1)
        return -1
    else:return dfs(tlst)

n=int(input())
times_lst=[]
for i in range(n):
    line=list(map(int,input().split()))
    times_lst.append(line)
print(times_lst)
lrtime=[]
for i in times_lst:
    s=(i[1]-i[0])//2+1
    early_lef=i[0]+s
    late_arr=i[1]-s
    lst=[early_lef,late_arr]
    lrtime.append(lst)
print(lrtime)
jud=dfs(lrtime)
print(jud)

N = int(input().strip())
alist = []
min_value = 24
max_value = 0
for i in range(N):
    alist.append(list(map(int, input().strip().split())))
    min_value = min(min_value, alist[i][0])
    max_value = max(max_value, alist[i][1])

last_chac = 0  # 开始欢迎第i场次初始化
dict_zhut = {i: {} for i in range(N+1)}
last_index = 0
dict_zhut[last_chac][last_index] = [0]*(max_value-min_value)  (3098)# 初始化


def MergeHuanying(dict_zhut, last_chac, last_index, alist):
    chac = last_chac+1
    if chac >= N+1:
        return 1
    start = alist[chac-1][0]-1   # 开始下标
    end = alist[chac-1][1]-1   (3099)# 结束下标
    len_huany = (end-start)//2+1
    num = end-(len_huany+start)+1
    for i in range(num):
        dict_zhut[chac][i] = dict_zhut[last_chac][last_index][:]
        huany = True
        # 检测可否欢迎本场次
        for j in range(start+i, start+i+len_huany):
            if dict_zhut[chac][i][j] == 1:
                huany = False
                break
        if huany:  (3100)# 可欢迎
            dict_zhut[chac][i][start+i:start+i+len_huany] = [1]*len_huany
            value = MergeHuanying(dict_zhut, chac, i, alist)
            if value == -1:
                continue
            else:
                return 1
    return -1


result = MergeHuanying(dict_zhut, last_chac, last_index, alist)
print(result)

#include <iostream>
(720)#include <vector>
#include <map>
(747)#include <algorithm>
 
using namespace std;
 
static bool cmp(pair<int, int>& a, pair<int,int>& b) {
    if (a.second - a.first != b.second - b.first)
        return (a.second-a.first) < (b.second-b.first);
    return a.first < b.first;
}

bool Complete(vector<pair<int, int>>& table, int pos, map<int, int>& dict) {
    if (pos >= table.size()) return true;

    int start = table[pos].first;
    int end  = table[pos].second;
    int diff = (end - start)/2 + 1;
    bool res = false;

    for (int i=start; i<=end-diff; i++) {
        auto itup = dict.upper_bound(i);
        auto itlo = dict.lower_bound(i);

        if (itup != dict.end()) {
            if (itup->first < i+diff) continue;
            if (itup != dict.begin()) if (prev(itup)->second > i) continue;
        }
            
        if (itlo != dict.begin()) {
            if (itlo->first==i || prev(itlo)->second > i) continue;
            if (itlo != dict.end()) if (next(itlo)->first < i+end) continue;
        }
        dict[i] = i+diff;
        res = res || Complete(table, pos+1, dict);
        if (res) return true;
        dict.erase(i);
    }

    return res;
}

int main() {
    int N;

    while (cin >>  N) {
        vector<pair<int, int>> table;
        map<int, int> dict;
        int start, end;

        for (int i=0; i<N; i++) {
            cin >> start >> end;

            table.push_back({start, end});
        }

        sort(table.begin(), table.end(), cmp);
        
        if (Complete(table, 0, dict)) cout<<1<<endl;
        else cout<<-1<<endl;
    }
}