Sachverhalt:
A.
Am 9. August 2012 erteilte die Gemeinde Vaz/Obervaz der C._ AG (Bauherrin) die Bewilligung zum Abbruch eines Stalls und zum Neubau von zwei Mehrfamilienhäusern mit Restaurant auf den Parzellen Nrn. 3862 und 2863 in Lenzerheide.
A._ und die B._ AG sind Eigentümer von Stockwerkeinheiten auf einer an das Baugrundstück angrenzenden Parzelle.
Am 2. Mai 2016 machten namentlich A._ und der Verwaltungsratspräsident der B._ AG geltend, die der Bauherrin erteilte Baubewilligung sei infolge unbenutzten Ablaufs der zweijährigen Bauvollendungsfrist gemäss Art. 91 des Raumplanungsgesetzes für den Kanton Graubünden vom 6. Dezember 2004 (KRG) hinfällig geworden, weshalb das Baugesuch nochmals neu aufzulegen und auszuschreiben sei.
Am 25. Mai 2016 ersuchte die Bauherrin die Gemeinde Vaz/Obervaz darum, die Bauvollendungsfrist gemäss Art. 91 KRG bis Ende Juni 2017 zu verlängern und machte geltend, diese Frist sei unter Berücksichtigung der kommunalen Bausperren noch nicht abgelaufen.
Mit Entscheid vom 14. Juli 2016 hiess der Gemeindevorstand Vaz/Obervaz das Gesuch um Verlängerung der Frist zur Fertigstellung der Bauten auf der Parzelle Nr. 3862 gut und erstreckte diese Frist bis 30. Juni 2017.
Zur Begründung führte der Gemeindevorstand an, die im kommunalen Baugesetz vorgesehenen Bausperren während der Wintersaison seien bei der Berechnung der Bauzeiten zu berücksichtigen. Demnach habe während weniger als 21,5 Monaten gebaut werden können, weshalb das Verlängerungsgesuch innerhalb der zweijährigen Frist gestellt worden sei. Bezüglich der Bewilligung einer Verlängerung sei eine Interessenabwägung zwischen dem privaten Interesse des Bauherrn an der Fertigstellung der Baute gemäss der Baubewilligung und dem öffentlichen Interesse an der Durchsetzung allfälliger seither eingetretener Rechtsänderungen vorzunehmen. Die Baubewilligung vom 9. August 2012 lasse die Erstellung von Zweitwohnungen zu. Seither sei jedoch am 1. Januar 2016 das Bundesgesetz über Zweitwohnungen vom 20. März 2015 (Zweitwohnungsgesetz, ZWG) in Kraft getreten, das in der Gemeinde Vaz/Obervaz den Bau von neuen Zweitwohnungen verbiete. Das private Interesse an der Fertigstellung der Bauten gemäss der Baubewilligung sei vorliegend stärker zu gewichten als das öffentliche Interesse an der Umsetzung des Zweitwohnungsgesetzes, weshalb die Fristverlängerung bis am 30. Juni 2017 zu gewähren sei.
B.
Eine dagegen von A._ und der B._ AG erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden mit Urteil vom 1. Februar 2017 ab.
C.
A._ und die B._ AG (Beschwerdeführer) erheben Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das Urteil des Verwaltungsgerichts vom 1. Februar 2017 sowie die im Entscheid des Gemeindevorstands Vaz/Obervaz vom 14. Juli 2016 gewährte Fristverlängerung zur Fertigstellung der Bauten auf der Parzelle Nr. 3862 seien aufzuheben und die Gemeinde Vaz/Obervaz sei anzuweisen, das Bauvorhaben nochmals gesetzeskonform auszuschreiben.
Das Verwaltungsgericht schliesst unter Verweis auf die Ausführungen im angefochtenen Entscheid auf Abweisung der Beschwerde. Die Gemeinde Vaz/Obervaz und die Bauherrin (Beschwerdegegnerin) beantragen, die Beschwerde abzuweisen, soweit darauf einzutreten sei.
Die Beschwerdeführer reichten zu den Vernehmlassungen eine Stellungnahme ohne neue Anträge ein.

Erwägungen:
1.
1.1. Das Bundesgericht prüft seine Zuständigkeit von Amtes wegen (<ref-law>). Es untersucht deshalb grundsätzlich von Amtes wegen, ob und inwiefern auf eine Beschwerde eingetreten werden kann. Da die Beschwerde gemäss <ref-law> hinreichend zu begründen ist, ist in der Beschwerde darzulegen, dass die gesetzlichen Legitimationsvoraussetzungen gegeben sind, soweit diese nicht ohne weiteres ersichtlich sind (<ref-ruling> E. 2 S. 403 f.).
1.2. Gemäss <ref-law> ist zur Beschwerde in öffentlich-rechtlichen Angelegenheiten berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten hat (lit. a), durch den angefochtenen Entscheid besonders berührt ist (lit. b). Verlangt ist somit neben der formellen Beschwer, dass der Beschwerdeführer zur Streitsache über eine spezifische Beziehungsnähe verfügt. Diese Nähe muss bei Bauprojekten insbesondere in räumlicher Hinsicht gegeben sein (<ref-ruling> E. 2.3 S. 219 f.; <ref-ruling> E. 2.2.2 S. 34; Urteil 1C_203/2016 vom 19. August 2016 E. 3.2; je mit Hinweisen). Zudem verlangt <ref-law>, dass der Beschwerdeführer ein schutzwürdiges Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids besitzt. Nach der Rechtsprechung setzt dieses Interesse voraus, dass dem Beschwerdeführer im Falle des Obsiegens ein praktischer Nutzen entsteht. Ein solcher Nutzen ist bei Streitigkeiten über Baubewilligungen grundsätzlich zu bejahen, wenn das Durchdringen von Rügen des Beschwerdeführers sich rechtlich oder tatsächlich auf seine Stellung auswirken würde, indem das Bauvorhaben, soweit es ihn belastet, nicht oder anders realisiert würde als geplant (<ref-ruling> E. 2.2 S. 504 mit Hinweisen). Nicht zulässig ist hingegen das Vorbringen von Beschwerdegründen, mit denen einzig ein allgemeines öffentliches Interesse an der richtigen Anwendung des Rechts verfolgt wird, ohne dass den Beschwerdeführenden im Falle des Obsiegens ein Vorteil entsteht (BGE <ref-ruling> E. 2.2.3 S. 33 mit Hinweis).
1.3. Die Vorinstanz führte aus, die Beschwerdeführer seien als Eigentümer von Stockwerkeinheiten auf einem unmittelbar an das Baugrundstück angrenzenden Grundstück von der strittigen Fristverlängerung besonders berührt. Die Gutheissung ihrer Beschwerde würde ihnen offensichtlich einen praktischen Nutzen bringen, da nach Ablauf der zweijährigen Bauvollendungsfrist die Baubewilligung von Gesetzes wegen erlösche.
1.4. Vor Bundesgericht bringen die Beschwerdeführer vor, ihre direkte Betroffenheit sei ausgewiesen. Würde die Beschwerde gutgeheissen, wäre die Baubewilligung hinfällig und das Baubewilligungsverfahren sei, da die beiden Gebäude grossmehrheitlich fertiggestellt seien, neu durchzuführen. Dabei könnten infolge der veränderten Gesetzgebung mit Bezug auf die Zweitwohnungen allenfalls Nachteile zu Lasten der Bauherrschaft resultieren, da eventuell sogar Erstwohnungen geschaffen würden.
1.5. Gemäss diesen Ausführungen gehen die Beschwerdeführer davon aus, die Gutheissung ihrer Beschwerde führe dazu, dass die Beschwerdegegnerin zur Vollendung der Bauten ein neues Baugesuch einreichen müsse. Zudem bringen die Beschwerdeführer dem Sinne nach vor, dass infolge des nachträglichen Inkrafttretens des Zweitwohnungsgesetzes bezüglich einer erneuten Baubewilligung allenfalls Nachteile zu Lasten der Bauherrschaft resultieren könnten, da nur Erstwohnungen geschaffen werden könnten. Sie machen damit implizit geltend, dass in der Gemeinde Vaz/Obervaz der zulässige Zweitwohnungsanteil überschritten sei und daher gemäss Art. 7 Abs. 1 lit. a und b ZWG neue Wohnungen nur bewilligt werden dürften, wenn sie als Erstwohnung oder als touristisch bewirtschaftete Wohnung genutzt werden. Inwiefern eine entsprechende Nutzungsbeschränkung gemäss <ref-law> für die Beschwerdeführer einen Nutzen bzw. einen praktischen Vorteil bringen soll, legen sie jedoch nicht dar. Sie machen nicht geltend, eine solche Nutzungsbeschränkung würde dazu führen, dass die Beschwerdegegnerin auf die Fertigstellung der Bauten ganz oder teilweise verzichte. Dies ist auch nicht ersichtlich, da die Bauten gemäss den Angaben der Beschwerdeführer bereits grossmehrheitlich errichtet wurden und die Beschwerdegegnerin in ihrer Beschwerdeantwort ausführt, die Bauten seien heute - abgesehen vom Endausbau einzelner Wohnungen - fertiggestellt und bereits abgenommen. Die Beschwerdeführer bringen auch nicht vor, die zulässige Nutzung der Bauten als Erstwohnungen oder als touristisch bewirtschaftete Wohnungen sei für sie vorteilhafter bzw. weniger belastend als eine Nutzung als Zweitwohnungen, was auch nicht ohne weiteres ersichtlich ist. Demnach ist mangels eines praktischen Nutzens der Beschwerdeführer im Falle des Obsiegens auf die Beschwerde nicht einzutreten.
1.6. Diese wäre im Übrigen in der Sache unbegründet. Die Beschwerdeführer rügen einzig, die vorinstanzliche Annahme, die Frist zur Bauvollendung gemäss Art. 91 KRG werde durch saisonale kommunale Baubeschränkungen oder gerichtliche Bauverbote gehemmt, sei willkürlich. Zur Begründung bringen die Beschwerdeführer zusammengefasst vor, Art. 91 KRG sehe eine solche Hemmung nicht vor, obwohl die winterlichen Bausperrfristen in verschiedenen Tourismusgemeinden bekannt gewesen seien. Demnach sei insoweit von einem qualifizierten Schweigen auszugehen, zumal Art. 91 KRG ausdrücklich zulasse, eine Fristverlängerung zu beantragen. Aufgrund der klaren gesetzlichen Regelung müsse deshalb in Anwendung der allgemeinen Auslegungsregeln darauf geschossen werden, von der Bauvollendungsfrist gemäss Art. 91 KRG dürften - abgesehen von der Gutheissung eines rechtzeitig eingereichtes Verlängerungsgesuchs - keine weiteren Ausnahmen zugelassen werden.
Ob ein qualifiziertes Schweigen des Gesetzgebers vorliegt, ist durch Auslegung zu ermitteln (<ref-ruling> E. 1.4.2 S. 55 mit Hinweis). Die für ein solches Schweigen angeführten Argumente der Beschwerdeführer sind nicht zwingend, da die Vorinstanz für ihre Auslegung nachvollziehbare Gründe anführte. Demnach ist die vorinstanzliche Auslegung von Art. 91 KRG nicht unhaltbar, weshalb ein Verstoss gegen das Willkürverbot zu verneinen ist (vgl. <ref-ruling> E. 2.2 S. 72 mit Hinweisen).
2.
Nach dem Gesagten ist auf die Beschwerde nicht einzutreten. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (Art. 66. Abs. 1 BGG). Diese haben der anwaltlich vertretenen privaten Beschwerdegegnerin unter solidarischer Haftbarkeit eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1, 2 und 4 i.V.m. <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 1'500.-- werden den Beschwerdeführern auferlegt.
3.
Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 2'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Gemeinde Vaz/Obervaz und dem Verwaltungsgericht des Kantons Graubünden, 5. Kammer, schriftlich mitgeteilt.
Lausanne, 26. Juli 2017
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Merkli
Der Gerichtsschreiber: Gelzer