双指针

public class DoublePoint {
  final static int N = 100010;

  /**
   * idea:
   *    将 O(N^2) 的时间复杂度优化到 O(N)
   * step:
   *    1. 暴力做法
   *    2. 优化为双指针
   */
  private static void template() {
    for (int i = 0, j = 0; i < N; i ++) {
      while (j < i && Tools.check(i, j)) j++;
      // 每道题的具体逻辑
    }
  }
}

位运算

public class BitOperation {
  /**
   * description:
   *    求一个数的二进制表示中的第 N 位是多少
   * step:
   *    1. 先把第 K 位移动到最后一位
   *    2. 看该位是多少
   */
  public static int goLeftNBit(int num, int step) {
    return num >> step & 1;
  }

  public static int lowBit(int num) {
    return num & -num;
  }
}

区间合并

public class IntervalMerge {
	/**
   * description:
   *    区间合并算法
   */
  private static int merge(ArrayList<PII> segs) {
  	ArrayList<PII> ret = new ArrayList<>();
    
    // 排序
    PII[] a = segs.toArray(new PII[0]);
    Arrays.sort(a, 0, a.length, 
        Comparator.comparing(o -> ((PII) o).first)
            .thenComparing(o -> ((PII) o).second));
    
    // 初始化区间
    final int MIN = (int) -2e9;
    int st = MIN, ed = MIN;
    
    // 遍历区间
    for (var item : a) {
      // 判断是否为一个新区间
      if (ed < item.first) {
        // 记录之前的区间
        if (st != MIN) ret.add(new PII(st, ed));
				// 更新区间
        st = item.first; ed = item.second;
        // 为连续区间则更新区间尾部指针
      } else ed = Math.max(ed, item.second);
    }
    
    // 加上最后一次的区间
    if (st != MIN) ret.add(new PII(st, ed));
    
    return ret.size();
  }
  
  public static void main(String[] args) {
    ArrayList<PII> segs = new ArrayList<>();
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] line = in.readLine().spilt(" ");
    
    int n = Integer.parseInt(line[0]);
    for (int i = 0; i < n; i++) {
      line = in.readLine().spilt(" ");
      int l = Integer.parseInt(line[0]), r = Integer.parseInt(line[1]);
      segs.add(new PII(l, r));
    }
    
    System.out.println(merge(segs));
  }
}

离散化

调了半天没调好，先放一放吧(*´﹃｀*)

参考来源

• Acwing - 算法基础课