vivek_ragi

Insert_Interval

Jul 13th, 2021
700
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     static bool compare (vector<int> &v1, vector<int> &v2) {
  4.         //cout <<"HA";
  5.         if (v1[0] == v2[0]) {
  6.             return v1[1] < v2[1];
  7.         }
  8.         return v1[0] < v2[0];
  9.     }
  10.     vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
  11.         int n = intervals.size();
  12.         vector<vector<int>> ans;
  13.         //edge cases
  14.         if (n == 0) {
  15.             ans.push_back({newInterval[0],newInterval[1]});
  16.             return ans;
  17.         }
  18.         int cnt = 0;
  19.         for (int i = 0; i < n; ++i) {
  20.             if (intervals[i][1] >= newInterval[0] and intervals[i][0] <= newInterval[1]) {
  21.                 intervals[i][0] = min(intervals[i][0], newInterval[0]);
  22.                 intervals[i][1] = max(intervals[i][1], newInterval[1]);
  23.                 cnt++;
  24.             }
  25.         }
  26.         //edge cases
  27.         if (cnt == 0) {
  28.             intervals.push_back({newInterval[0], newInterval[1]});
  29.             sort(intervals.begin(), intervals.end(), compare);
  30.             return intervals;
  31.         }
  32.        
  33.         sort(intervals.begin(), intervals.end(), compare);
  34.        
  35.         int index = 0;
  36.        
  37.         for (int i = 1; i < n; ++i) {
  38.             if (intervals[index][1] >= intervals[i][0]) {
  39.                 intervals[index][0] = min(intervals[index][0], intervals[i][0]);
  40.                 intervals[index][1] = max(intervals[index][1], intervals[i][1]);
  41.             }
  42.             else {
  43.                 index++;
  44.                 intervals[index] = intervals[i];
  45.             }
  46.         }
  47.        
  48.        
  49.        
  50.         for (int i = 0; i <= index; ++i) {
  51.             ans.push_back({intervals[i][0],intervals[i][1] });
  52.         }
  53.        
  54.         return ans;
  55.     }
  56. };
RAW Paste Data