İclas Otaqları II LeetCode Həlli


Tez-tez soruşulur Amazon Bloomberg ByteDance eBay Facebook Goldman Sachs google microsoft Kahin Quora Snapchat Swiggy cuqquldamaq Über VMware Walmart Laboratoriyaları
LeetCode LeetCodeSolutionsBaxılıb 60

Problem bəyanat

The İclas Otaqları II LeetCode Həlli – “İclas Otaqları II” sizə “intervallar[i] = [ başlanğıc[i], son[i] ]”, geri qaytarılan görüş vaxt intervalları “intervalları” verildiyini bildirir. minimum sayı konfrans otaqları tələb olunur.

Misal:

İclas Otaqları II LeetCode HəlliPin

intervals = [[0,30],[5,10],[15,20]]
2

Explanation:

Görüş 1-ci forma 0-dan 30-a qədər olan konfrans zalında edilə bilər.

İkinci görüş 2-ci forma 5-10 konfrans zalında edilə bilər.

M2 görüş 15-20 nömrəli konfrans zalında edilə bilər, çünki bu intervalda pulsuzdur.

intervals = [[7,10],[2,4]]
1

Explanation:

Görüş 1-ci forma 2-dan 4-a qədər olan konfrans zalında edilə bilər.

İkinci görüş bu intervalda pulsuz olduğu üçün 1 forma 7-10 konfrans zalında edilə bilər.

Yanaşma

Idea:

İki saxlamaq sıralanmış massivlər, bunlardan biri görüşlərin başlama vaxtını, digəri isə bitmə vaxtını saxlayır. Sonra başlanğıc massivi və son massiv üzərində təkrarlamaq üçün iki göstəricili ("i" başlanğıc massivi və son massiv "j" üçün iteratoru çağıraq) metodundan istifadə edin. Biz, həmçinin bir çox konfrans otağına ehtiyac duyacağımız üçün davam edən eyni vaxtda görüşlərin cari sayını saxlayacaq dəyişən “curr” saxlayacağıq.

  • start[i] < end[j] olarsa, bu o deməkdir ki, j-ci iclas hələ də davam edir və bizim i-ci görüş üçün başqa otağa ehtiyacımız var, buna görə də "curr"-u bir artıracağıq və "i"-ni də artıracağıq, biz i-ci iclasa başladıq.
  • start[i] >= end[j] olarsa, bu o deməkdir ki, j-ci iclas bitdi və o otaq indi boşdur, buna görə də j-ci görüş kimi 'curr'u bir azaldacağıq və 'j'i artıracağıq. bitdi.

İndi cavabımız proses boyu 'curr' in ən yüksək dəyəridir.

Kodu

İclas Otaqlarının C++ Proqramı II:

#include <bits/stdc++.h>
using namespace std;
int minMeetingRooms(vector<vector<int>> &intervals)
{
    vector<int> start;
    vector<int> end;
    for (int i = 0; i < intervals.size(); i++)
    {
        start.push_back(intervals[i][0]);
        end.push_back(intervals[i][1]);
    }
    sort(start.begin(), start.end());
    sort(end.begin(), end.end());
    int i = 1, j = 0, curr = 1;
    int answer = 1;
    while (i < start.size() && j < end.size())
    {
        if (start[i] < end[j])
        {
            curr++;
            i++;
        }
        else
        {
            curr--;
            j++;
        }
        answer = max(answer, curr);
    }
    return answer;
}
int main()
{
    vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
    cout << minMeetingRooms(intervals);
    return 0;
}
2

Yığıncaq Otaqlarının JAVA Proqramı II:

import java.util.Arrays;

public class TutorialCup {
    public static int solve(int[][] intervals) {
        int n = intervals.length;
        int[] start = new int[n];
        int[] end = new int[n];

        for (int i = 0; i < n; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int i = 1, j = 0, curr = 1;
        int answer = 1;
        while (i < start.length && j < end.length) {
            if (start[i] < end[j]) {
                curr++;
                i++;
            } else {
                curr--;
                j++;
            }
            answer = Integer.max(answer, curr);
        }
        return answer;
    }

    public static void main(String[] args) {

        int[][] intervals = { { 0, 30 }, { 5, 10 }, { 15, 20 } };
        System.out.println(solve(intervals));
    }
}
2

Yığıncaq otaqları üçün mürəkkəbliyin təhlili II LeetCode Həll

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (nlogn) çünki biz massivlərin çeşidlənməsi.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (n) çünki biz 'start' və 'end' massivlərindən istifadə edirik.

arayış https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html

Şərh yaz

Translate »
4