قرارست برنامه‌ای بنویسیم که ‎$1 \le n \le 1000$‎ بازه (به‌صورت ‎$[\text{begin},\text{end}]$‎) از ورودی خوانده و بازه‌های تکراری را از میان آن‌ها حذف کرده و سپس بازه‌های باقی‌مانده را الزاماً به همان ترتیب ورودی در خروجی بنویسد. در صورتی که یک بازه چند بار تکرار شده باشد، تنها اوّلین بار وقوع آن باید باقی بماند و سایر دفعات تکرار باید حذف شوند.

برای رسیدن به این هدف برنامه‌ی زیر و تابع DeleteRepeatedIntervals‎ نوشته شده است. این تابع را با کمک توابع ‎STL‎ و ‎…‎ در حداقل تعداد خط کامل کنید.

شما مجاز به تعریف حداکثر ‎۲‎ تابع دیگر و حافظه‌ی ‎$O(1)$‎ اضافی هستید. دقت کنید که زمان اجرای برنامه‌ی شما باید از ‎$O(n^2)$‎ کم‌تر (و نه حتی مساوی) باشد.

#include <cstdio>
#include <algorithm>
 
int n;
struct R { 
  int begin, end, id;
} a[1000];
 
void DeleteRepeatedIntervals(R a[], int n) {
  // implement this function
}
 
int main() {
  scanf("%d", &n);
  for (int i=0; i<n; i++)
     scanf("%d %d", &a[i].begin, &a[i].end);
  DeleteRepeatedIntervals(a, n);
  for (int i=0; i<n; i++)
    printf("%d %d\n", a[i].begin, a[i].end);
  return 0;
}

• سوال بعد
• سوال قبل