摘要
Title: 906. 区间分组
Tag: 贪心、最大区间厚度
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

906. 区间分组

• 题意

  给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
  输出最小组数。

• 思路

  将问题转化为

  有若干个活动，第i个活动开始时间和结束时间是[$l_i$,$r_i$]，同一个教室安排的活动之间不能交叠，求要安排所有活动，少需要几个教室？

  有时间冲突的活动不能安排在同一间教室，与该问题的限制条件相同，即最小需要的教室个数即为该题答案。

  那么就可以将开始时间和结束时间放在一起排序，遇到开始时间就把需要的教室加1，遇到结束时间就把需要的教室减1，取过程中需要教室的最大值即可

  如何区分左右区间？
  用奇偶性来判断左右区间即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-14 23:15:56
  FilePath: \ACM\Acwing\906.py
  LastEditTime: 2022-03-14 23:15:56
  '''
  N = int(1e5 + 10) * 2
  
  a = []
  n = int(input())
  idx = 0
  for i in range(n):
      l, r = map(int, input().split())
      a.append(l * 2) 
      a.append(r * 2 + 1)
  
  a.sort()
  res, cnt = 0, 0
  for i in range(len(a)):
      if a[i] % 2 == 0:
          cnt += 1
      else:
          cnt -= 1
      res = max(res, cnt)
  print(res)