608C - Chain Reaction - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;

  cin >> n;

  vector<pair<int, int>> v(n);
  vector<int> dp(n);

  for (int i = 0; i < n; i++) {
    cin >> v[i].first >> v[i].second;
  }

  int ans = INT_MAX;

  sort(v.begin(), v.end());

  dp[0] = 0;
  for (int j = 1; j < n; j++) {
    int l = 0, r = j - 1;
    int pos = -1;

    while (l <= r) {
      int mid = (l + r) / 2;

      if (v[mid].first >= v[j].first - v[j].second) {
        r = mid - 1;
      } else {
        l = mid + 1;
        pos = mid;
      }
    }

    if (pos != -1) {
      dp[j] = dp[pos] + (j - pos - 1);
    } else {
      dp[j] = j;
    }
  }

  for (int i = 0; i < n; i++) {
    ans = min(ans, dp[i] + (n - i - 1));
  }

  cout << ans << '\n';
}